数据结构-KMP算法_数据结构 kmp算法

本人水平有限，如有理解错误，表达错误，请评论指出，谢谢！

在我的理解，KMP算法最核心的同时最难理解的是这个next()函数。但是，next()的值是挺好求的，难在哪呢？

这个函数难在逻辑。理解起来很费劲，但真的很好用，并且这个函数的结果很好求。例如求模式串T=“ababaaa"的next[j]的函数值

是这样的，当j=0，next[0]=-1，对于任何子串，第一个元素的next()函数值都为-1

当j=1时，next[1]=0;

当j=2时，next[2]=0，因为t1!=t0。

当j=3时，next[3]=1，因为t0=t2。

当j=4时，next[4]=2，因为t0t1=t2t3='ab'。

当j=5时，next[5]=3，因为t0t1t2=t2t3t4='aba'。

当j=6时，next[6]=1，因为t5=t0='a'。

是的，看懂了吗，next[]的值其实就是看子串的前k个值与字串当前位置（没匹配上）的前k个是否相等，next[j]=k。

之后，说完这个函数，可以直接对KMP算法进行总结：

设s为主串，t为模式串，i为主串当前比较字符的下标，j为模式串当前比较字符的下标。令i=start,j初值为0，当si=tj时，i和j分别增加1，再继续比较

否则，i的值不变，j的值改变为next【j】的值再继续比较。这时分俩种情况

1.j 退回到某个j=next【j】值时，Si=Tj,此时i和j分别加1，继续比较

2.j退回到j= -1，令 主串跟模式串的下标各增加1，接着比较Si+1和T0,

这样的循环过程直到下标i大于等于主串，或下标j大于等于模式串t的长度时为止。