题目：
对于具有N个字符的给定字符串S的每个前缀（每个字符具有介于97和126之间的ASCII代码），我们想知道该前缀是否是周期性字符串。也就是说，对于每个i（2 <= i <= N），我们想要知道最大的K> 1（如果有的话），使得长度为i的S的前缀可以写为AK，即A级联K时间，对于一些字符串A.当然，我们也想知道时期K.
输入
包含几个测试用例。每个测试用例包含两行。第一行包含N（2 <= N <= 1 000 000） - 字符串S的大小。第二行包含字符串S.输入文件以一行结束，具有
数字为零。
输出
对于每个测试用例，在一行输出“测试用例＃”和连续的测试用例编号;然后，对于具有周期K> 1的长度为i的每个前缀，输出前缀大小i和由单个空格分隔的周期K;前缀大小必须按递增顺序排列。在每个测试用例后打印一个空行。
样本输入
3 AAA 12 aabaabaabaab 0
样本输出
测试案例＃1 2 2 3 3 测试案例＃2 2 2 6 2 9 3 12 4
解题思路：这个题主要考的是KMP中next[ ]数组的理解，next[k]指的是在k之前有一个长度为next[k]的字符串是字串的前缀。这个题的意思是找字符串前缀中循环的周期最大，也就是当循环体最小的时候，循环的周期才能最多。例如样例中 2 2指的是前缀的长度aa是2，然后循环体是a,循环的周期是2.
程序代码：
#include<stdio.h> #include<string.h> char s[2001000]; int n,next[2001000],t; void get(); int main() { int cas=1; while(scanf("%d",&n),n!=0) { int i,j,k; memset(s,0,sizeof(s)); memset(next,0,sizeof(next)); scanf("%s",s); printf("Test case #%d\n",cas++); get(); for(k=2;k<=n;k++) { t=k-next[k];//最小的循环体 // printf("<<%d %d\n",k,next[k]); if(t!=k&&k%t==0)//当k%t为整数时，才能求最大循环周期 printf("%d %d\n",k,k/t); } printf("\n"); } return 0; } void get() { int i=1,j=0; next[0]=-1; while(i<n) { if(j==-1||s[i]==s[j]) { i++; j++; next[i]=j; } else j=next[j]; } /* for(i=0;i<=n;i++) printf("%d ",next[i]); printf("\n");*/ }
