篇首语：本文由小编为大家整理，主要介绍了KMP的next数组求法详解相关的知识，希望对你有一定的参考价值。
近几天学习kmp算法，在next数组求解上受苦颇深，看了不少博客，感觉写得都不够清晰，所以想按照自己理解的过程来尝试写一下，也便于以后温习。
关于kmp算法的介绍，网上博文有很多，就不再赘述，推荐一篇kmp算法，个人感觉挺好
这里主要详细讲解next数组的求解。
由于在下不擅作图，有的地方单纯用文字描述不够清晰，还请原谅。
若有什么地方写得不对欢迎批评，以便于在下修正。
kmp算法的精髓就在于next数组，从而达到跳跃式匹配的高效模式。
而next数组的值是代表着字符串的前缀与后缀相同的最大长度,(不能包括自身)。
这里举个例子：
模式串t A B A B A A下标 0 1 2 3 4 5next 0 0 1 2 3 1next[0]代表t[0]~t[0]即"A"的最大前后缀，显然为0.next[1]代表t[0]~t[1]即"AB"的最大前后缀，为0.next[2]代表t[0]~t[2]即"ABA"的最大前后缀，即"A",长度为1.next[3]代表t[0]~t[3]即"ABAB"的最大前后缀，即"AB",长度为2. next[4]代表t[0]~t[4]即"ABABA"的最大前后缀，即"ABA",长度为3.next[5]代表t[0]~t[5]即"ABABAA"的最大前后缀，即"A",长度为1.看到这里，next值代表的意义应该可以明白了。
但next数组怎样用代码去求呢，我们当然不可能挨个去比较前后缀。
仍然是上面那个例子
A B A B A A
初始化，next[0]为0；
t[0] != t[1] next[1]为0；
t[0] == t[2] next[2]为1；
在求next[3]时，比较t[1]和t[3]是否相等？
相等：显然 next[3] = next[2]+1;
不相等：怎么办？ 看下面
void makeNext(char s[],int next[]) int len = strlen(s); next[0]=0; //初始化 for(int i=1,k=0;iwhile(k>0 && s[k]!=s[i]) //这个while是最关键的部分 k=next[k-1]; //等价于 k=next[next[i-1]-1] //等号右边的k起的只是下标的作用 if(s[k]==s[i]) k++; //相等就+1 next[i]=k; //赋值 例子说话
A B A B A B A C
0 1 2 3 4 5 6 7
next[6] = 5
即前缀为t[0]~t[4] 后缀为t[2]~t[6]
next[4] = 3
即前缀为t[0]~t[2] 后缀为t[2]~t[4]
我们发现
next[4]的前缀一定是next[6]的前缀
next[4]的后缀也一定是next[6]的后缀
(这是while循环的原理，可以试着举个例子验证一下)
现在我们要求next[7]，将t[7]与t[5] ( t[next[6]] )比较，发现不相等
那么可以将t[7]与t[3] (t[ next[next[6]-1] ])比较，如果相等，则next[7] = next[4] +1 ;
不相等就重复此过程，直到t[7]与t[0]比较.
上框内过程其实就是代码中，while循环里的内容，现在回过头去看上面代码应该会顺畅很多。
下面附上kmp完整代码
/************************************************************************* > File Name: kmp.cpp > Author: > Mail: 458241107@qq.com > Created Time: 2015年10月12日 星期一 18时32分00秒 ************************************************************************/#include<iostream>#includewhile(k>0 && s[k]!=s[i]) k=next[k-1]; if(s[k]==s[i]) k++; next[i]=k; int kmp(char t[],char s[]) int len1 = strlen(t); int len2 = strlen(s); int next[len2]; makeNext(s,next); for(int i=0,j=0;iwhile(j>0 && t[i]!=s[j]) j=next[j-1]; if(t[i]==s[j]) j++; if(j==len2) return i-j+1; int main() char t[]="1234561123458412"; char s[]="611"; cout<cout<cout<<"下标为"< 以上是关于KMP的next数组求法详解的主要内容，如果未能解决你的问题，请参考以下文章
