对于KMP算法中的next数组大家估计都不是很陌生。
但是，next数组的意义好像是一知半解。不过next数组的博大精深，令我小辈唏嘘。
一般的next求解：
void Get_Next(){
next[0]=-1;
int j=-1,i=0;
while(i<len){
if(j==-1||str[j]==str[i]){
j++;i++;
next[i]=j;
}
else j=next[j];
}
}
代码很是简单。
我们知道，在运行KMP算法的时候，模式串和主串失配的时候，主串不动（失配位置为i），我们就可以将模式串的失配位置j，移到next[j]位置，继续进行匹配。从而减少了很多的不必要的匹配。
那么next数组的具体意义在什么地方呢？那么为什么当失配的时候可以将模式串的位置移到next[j]呢？
我们知道，可以移到next[j]，是因为，模式串中从第一个字符到低next[j]个字符和从第j-next[j]到第j和字符是一样的。看下图：
其实到这里，我们是可以看出来的，next[i]数组的实际意义就是前i个字符前缀和后缀的最大匹配数。
那么我们可以用这个数组来作什么呢？？？
第一，求字串中【前缀+跟前缀相同的子串】的个数，详细看这篇文字：点击打开链接
第二，求一个字符串的最短周期。
我们知道，根据next数组的理解，next[i]就是指前i个字符串中，前缀和后缀的最大匹配数。
那么我们可以得到结论，i-next[i]就是前i个字符的最短周期。
为什么？？对，凡事不懂，要问为什么。
几个例子：
推荐做几道题目：Hdu3746 Cyclic Nacklace点击打开链接
Hdu1358 Period 点击打开链接 都是又换周期的问题。
好了KMP就先了解到这里，接下来要弄AC自动机了。