首先要了解KMP算法中的next[]和nextval[]。
nexttval[]算是next[]的改进算法，不过就是s[k]、s[j]是否相等的区别。
我的理解是，假设a是源字符串，b是要进行匹配的字串，next[i]及nextval[]通过b串生成。i指向a串当前进行匹配的字符，j指向b串当前进行匹配的字符。
规定，next[]与nextval[]第一个元素的值为字符串起始元素序号减1。
next[j]是当b[j]失配（即a[i]!=b[j]）时，j往前跳的位置。能保证：b[0]到b[j-1]均与a[i]前j-1个字符（不包括a[i]本身）一一匹配；且此时next[j]能保证b[0]到b[next[j]-1]均与a[i]前next[j]-1个字符（不包括a[i]本身）一一匹配的，小于j的最大值。
nextval[i]与next[i]一样，只不过，b[j]有可能等于b[next[j]]，所以失配后，用next[]可能要跳几次才能找到a[i]与b[j]不同的值继续匹配；而b[j]不会等于b[nextval[j]]，所以失配后只需跳一次即可。
比如：
| |
a |
a |
a |
a |
b |
b |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
| next[] |
-1 |
0 |
1 |
2 |
3 |
0 |
| nextval[] |
-1 |
-1 |
-1 |
-1 |
3 |
0 |
| |
a |
b |
c |
a |
b |
d |
a |
b |
c |
a |
b |
d |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| next[] |
-1 |
0 |
0 |
0 |
1 |
2 |
0 |
1 |
2 |
3 |
4 |
5 |
| nextval[] |
-1 |
0 |
0 |
-1 |
0 |
2 |
-1 |
0 |
0 |
-1 |
0 |
2 |
应该讲得差不多了吧。下面是KMP算法的模板：
生成next[]的模板：（s为传入的字符串，l为s的长度，next[]为要生成的next数组；如果是string类型，则将“char s[]”改为“string s”即可）
void getNext(char s[],int len,int next[])
{ int i,k; i=0; k=-1;
next[0] = -1;
while(i < len)
{ if (k==-1 || s[i]==s[k])
{
k++; i++;
next[i]=k;
}
else k=next[k];
}
}
生成nextval[]的模板：（s为传入的字符串，l为s的长度，nextval[]为要生成的nextval数组；如果是string类型，则将“char s[]”改为“string s”即可）
void getNextVal(char s[],int len,int nextval[])
{ int i,k; i=0; k=-1;
nextval[0] = -1;
while(i < len)
{
if(k == -1 || s[i] == s[k])
{ k++; i++;
if(s[i] != s[k])
nextval[i] = k;
else nextval[i] = nextval[k];
}
else
k=nextval[k];
}
}
具体使用的实例：
1、POJ 2406 Power Strings
题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，
"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。
定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]
例子证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，
由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，
即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。
由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，
则最大循环次数n为len/(len - next[len])，否则为1。
2、POJ 3461 Oulipo