题目链接：http://vjudge.net/problem/viewProblem.action?id=29342
题目大意：给定字符串，找到每个前缀的最大循环节的个数。
首先当然是kmp预处理，接下来的问题是 怎么找循环节？
用反证法可以证明，如果f[i]~i之间的字符串能构成循环节，则该字符串就是i前缀对应的循环节，否则循环节不存在。
对每个前缀找到尾指针对应的失陪位置后，不需要按失陪指针继续往前寻找了（否则超时）。
只用判断上个位置到尾部的字符串是否是循环节(长度是否有整除关系），即知循环节个数。
代码奉上：
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring> int f[];
char p[];
void deal(int l){
f[]=-;
int i=,k=-;
while(i<l){
if(k==- || p[k]==p[i])f[++i]=++k;
else k=f[k];
}
//for(i=0;i<l;i++)printf("%d: %d\n",i,f[i]);
}
int main(){
int n,cs=;
while(scanf("%d",&n) && n){
scanf("%s",p);
deal(n);
printf("Test case #%d\n",cs++);
int i,k;
for(i=;i<=n;i++){
if(f[i]== || i%(i-f[i]))continue;
k=i/(i-f[i]);
if(k>)printf("%d %d\n",i,k);
}
printf("\n"); }
return ;
}
证明没有仔细说，不明白的欢迎留言讨论~