KMP算法初学者如何理解

本文主要是介绍KMP算法初学者如何理解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

关于 KMP 算法的个人理解（Java初学者）

大二上学期的时候，学习数据结构，偶尔接触了KMP算法，那个时候没特别理解，为了应付考试，就仅仅是看了前缀后缀那个知识点，刚刚打算好好看一看，因为最近在学习java，老师提到了一句，自己刚刚查阅资料研究的时候，感觉对于小白来说很难理解，一下是我的一些看法。

KMP算法的用处
在一个长的字符串里寻找一个短的字符串，有一种暴力解法，举个例子。
** a b a b a**
a b a
在ababa中寻找aba，可以这样对照。（粗的是一样的）如下图；

这个暴力求解，我们可以看出，只要主串足够长，那么在主串中寻找子串的位置就越难！假设主串长度是m，而子串长度是n , 那么这个计算相当于是一个双重循环！（如上图ababb中寻找abb）
先从主串a开始依次对比子串的abb，如果不对就从主串的b开始再依次对比子串的abb。就有点类似于
for(ababb){
for(abb){
}
}
这样显然是很慢的，那么有没有一种方法，因为子串是固定呢，能不能在往下移的时候多移一点呢？或者说省略一点点呢？比如直接在不同的地方跳过？

虽然上面我举的例子是错误的方法，但是这样我们就有了一个想法，当比较不同的时候，我们可以通过一些方式跳过一些步骤，从而省略时间！
既然我们知道了可以跳过一些步骤，具体要跳过多少步骤呢？从比较不同的地方开始跳跃吗？显然是错误的！这就是KMP算法的精髓！我们继续看例子(这次的例子可是正确的咯,也会反驳我之前那个错误的方法)
abaabaabac
abaabac
比如这个例子
很明显第七个位置是不同的，那么直接跳过6个步骤对吗？显然不对，因为只要跳过三个步骤就可以了
aba abaabac
abaabac
我们怎么看出的呢？
abaabaabac
abaabac
有没有发现这三个是相同的
我们就跳过三个步骤(6-3)
因为前6个都相同，所以6来源于这里，因为abaaba前面和后面有aba是相同的，所以是3

那么具体跳过几个步骤，如何来计算呢？这就是kmp算法中的next[ ]
NEXT[ i ] = j
这个数组有什么意思呢？
我们先来理解前缀和后缀
比如用ababa来举例
前缀就是从前开始 a,ab,aba,abab
后缀就是从后开始 a,ba,aba,baba
我们可以看出前缀和后缀相等的最大位数是aba，是三位
我们就可以这样表示 next[5]=3,
其中5是表示这个字符串一共有多少位数，3表示这个字符串前缀和后缀相等的最大位数
跳过的步骤就是 5 - 3 = 2
这就是 next[ ] 数组的用法
我们看之前例子
abaabaabac
abaabac 第七个出现不同，说明之前的6个都是符合的 （next[6]）
我们把之前的6个拿出来
abaaba
前缀a,ab,aba,abaa,abaab
后缀a,ba,aba,aaba,baaba
那么这个相等的就是aba
next[6]=3
所以我们跳过6-3个
aba abaabac
abaabac 就变成了这样
这样不会既不会因为减少步骤而落下一些相同的，也会减少时间
这就是KMP算法的精髓
如何用编程语言实现next[i]就需要自己更加的了解才可以!
理解了这个，KMP你就理解了大概了，就是在筛选过程中，跳过一些没有必要的过程来减少计算时间，这是我自己的理解！如果以后我有更好的讲解方法，我会再次更新帮助初学者们。

这篇关于KMP算法初学者如何理解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！