转载 - kmp next函数 kmp的周期问题，深入了解kmp中next的原理

出处：http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

kmp next函数 kmp的周期问题，深入了解kmp中next的原理

-----------------------

-----------------------

k    m        x      j       i

由上，next【i】=j，两段红色的字符串相等（两个字符串完全相等），s[k....j]==s[m....i]

设s[x...j]=s[j....i](xj=ji)

则可得，以下简写字符串表达方式

kj=kx+xj;

mi=mj+ji;

因为xj=ji，所以kx=mj，如下图所示

-------------

-------------

k   m        x     j

看到了没，此时又重复上面的模型了，kx=mj，所以可以一直这样递推下去

所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);