题目：
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.
分析：
该题求每个长度大于等于2的前缀连续出现的最大次数（从前缀的位置开始）。
我的next[i]表示和以这一位结尾的后缀相同的前缀的末尾的位置，如
a a b a a c
0 1 0 1 2 0
a a b a a b a a b a a b
0 1 0 1 2 3 4 5 6 7 8 9
我们发现这样一个规律：所有满足题目条件的，都满足 (i%(i-nxt[i])==0.
code
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int lena, lenb, nxt[1000005];
char a[1000005], b[1000005];
void mknxt(){
int j=0, k;
k = nxt[0] = -1;
while(j<lenb){
if(k==-1 || b[j]==b[k]) nxt[++j] = ++k;
else k = nxt[k];
}
}
int main(){
while(1){
cin>>lenb;
if(!lenb)break;
scanf("%s", b);
mknxt();
printf("Test case #%d\n",++lena);
for(int i=2; i<=lenb; i++) {
if(nxt[i]){
if(i%(i-nxt[i])==0){
printf("%d %d\n",i,i/(i-nxt[i]));
}
}
}
printf("\n");
}
return 0;
}