共计 2344 个字符，预计需要花费 6 分钟才能阅读完成。
KMP 算法其实理解起来也不难，只不过很多过于公式化的讲解以及太过晦涩的说法会让人一头雾水；
KMP 算法主要是判断一个字符串是否是另一个字符串的字串；对于这两个字符串，在算法描述中有固定的称谓：我们把最长的字符串称为 text，需要判定的子串称为模式 pattern;
对于这个问题，其实最容易想到的就是暴力枚举：即 text 字符串逐个字符判定，若当前第 i 字符和 pattern 首字符一样，进行 pattern 第二位的判定，如果中间有一个字符不同，则结束本轮判断，重新判断第 i + 1 个字符；该方法会达到 O(m*n) 级别；
而 KMP 算法就是处理该问题的更优算法，复杂度只有 O(m+n);
其实我们可以大致推断出暴力枚举的缺陷点，其根本的问题就是回溯。由于 pattern 字符串有可能会有某些规律，使得我们判断第 i 个字符失败的时候，不用从 i + 1 个开始重新判断，只需要判断 i + k 个，而 KMP 算法就是描述如何进行更优判断；
首先接触 KMP 算法，我们要理解 NEXT 数组，NEXT 数组针对的是 pattern 字符串，描述的是当前字符串的最长的相同前缀和后缀的长度；例如:ababa, 其最长的相同前缀后缀就是 aba，这个自己看一看就很清楚；
而 NEXT 数组保存的就是这些值。NEXT 数组索引是当前 0~i 子字符串的长度，其相应的数组值就是该长度下的相同前后缀的长度 k；
这里其实可以注意一下，由于给出的字符串坐标索引是从 0 开始，所以 k 也可以认为是最长前缀的最后一位的下标；对于这个数组，我们其实可以依次算出来，但是如果用程序化的语言描述，则应该使用递推来进行；具体代码如下：
void getNext(char s[],int len){
int j=-1;
next[0]=-1;
for(int i=1;i<len;i++){
while(j!=-1&&s[i]!=s[j+1]){
j=next[j];
}
if(s[i]==s[j+1]){
j++;
}
next[i]=j;
}
}
对于上述代码，可能有点不清晰，所以讲解一下：首先我们必定是从字符串开头算起，对于一个字符，我们无法计算他的前后缀，所以设置 -1，意为，没有前后缀；后续则从第二个字符进行判断；
首先理解 j，j 就是当前第 i 个字符需要比较的字符，为什么要比较，原因如下；假如出现如下情况：
我们当前 j 指向的是 b，需要比较的 i 指向的是 b，如果这两个相同，则前缀后缀都变成了 abb，其实 j 存在的意义就是判断能否继承之前的前后缀性质，既然 i -1,i- 2 和 j -1,j- 2 一样，都是 ab，那么如果下一位 i 和 j 都一样，那么就是 i,i-1,i- 2 和 j,j-1,j- 2 一样，都为 abb，则后缀前缀都变成 abb；
之前说过，NEXT 的内容代表的是相应长度下的最长前缀长度，因此，在相同的情况下，长度为 i 的串的前缀最大长度就应该是上述代码最后一行的 next[i]=j；
相等情况下很好理解，关键在于不想等情况的理解；自己参阅相关的文献。。。还想破头想了好久，发现不相等的情况其实就是两种情况的一种递归情况：借用该博客下的一张图：
其实说白了，当不相等就是一个向左递归找更小的序列，看能不能使得子序列里能够出现相同的前缀后缀；对于上述可能理解有点困难，可以举一个例子来看：假如有一个字符串 ccacbccace；i 指向 e，j+ 1 指向 b；此时进行判断，不相等；此时 NEXT[j] 就是 ccac 的最长前缀的最后一个索引，也就是 1，这个时候在进行 j + 1 和 i 的判断；为什么要这样，原因在于根本来说，因为出去 i 和 j，前缀和后缀相等，所以判断前缀 ccac 也就相当于判断后缀 ccac，所以前缀 ccac 的第一个需要判断的 c，该字符串的后缀也必定有；
当然，当时自己想到了另一种情况试图推翻，但是这种情况也无需考虑；例如：ccabd, 那么此时 d 前面不就和前缀不相同了？其实这种情况不可能出现，因为前面 j 指向第二个 c，所以比较的仍然是第一个元素；
所以总的来说，这就是一个递归向前的求更小前缀长度的操作。一旦向前得到的子序列有相同前缀和后缀，则第 i 个元素之前的后缀必定和该求得的前缀相同。否则，只能比较第一个元素，不可能得到更小的相同前缀后缀；
所以，next 数组求解就很简单；
接下来就是KMP算法，该算法就是利用 NEXT 函数求解；说到底 KMP 算法就是利用 pattern 的前后缀来进行操作的。
如上所示：：如果 D 和空格不匹配，此时由于 ABCDAB 有相同的前后缀所以替换的时候就把前缀和后缀重合，从而移动了 j -next[j] 个距离，从而到达以下位置：
所以也不难，主要是要怎么理解 Next 数组；相应代码如下所示：
bool KMP(char text[],char pattern[]){
int n=strlen(text),m=strlen(pattern);
getNext(pattern,m);
int j=-1;
for(int i=0;i<n;i++){
while(j!=-1&&text[i]!=pattern[j+1]){
j=next[j];
}
if(text[i]==pattern[j+1]){
j++;
}
if(j==m-1){
return;
}
}
return false;
}
如果需要重复计数：
int KMP(char text[],char pattern[]){
int n=strlen(text),m=strlen(pattern);
getNext(pattern,m);
int j=-1;
int ans=0
for(int i=0;i<n;i++){
while(j!=-1&&text[i]!=pattern[j+1]){
j=next[j];
}
if(text[i]==pattern[j+1]){
j++;
}
if(j==m-1){
ans++;
j=next[j];
}
}
return ans;
}
