题目描述
如果一字符串S由一字符串T重复K次形成，T是S的循环元。当K最大时字符串T为S的最小循环元，K为最大循环次数。
现输入一长为N的字符串S，对S的每一个前缀，如果它的最大循环次数大于1，输出该前缀的最小循环元长度和最大循环次数。
题解
对于样例aabaabaabaab，当第二个a时，a出现了2次；第二个b时，aab出现了两次；第三个b时，aab出现了3次；第四个b时，aab出现了4次。
通过求出字符串S的next数组，分析next数组含义可以发现，在查找S的第i位结尾的前缀时，如果i-next[i]能整除i，那么S[i~i-next[i]]就是前i位的最小循环元，最大循环次数为i/(i-next[i])。
#include<stdio.h> #include<string.h> using namespace std; char a[1000005]; int next[1000005],n; void cal() { next[1]=0; for(int i=2,j=0;i<=n;i++) { while(j>0&&a[i]!=a[j+1])j=next[j]; if(a[i]==a[j+1])j++; next[i]=j; } } int main() { int ans=0; for(int t=1;;t++) { scanf("%d",&n); getchar(); if(n==0)break; for(int i=1;i<=n;i++) scanf("%c",&a[i]); printf("Test case #%d\n",t); cal(); for(int i=1;i<=n;i++) if(i%(i-next[i])==0&&i/(i-next[i])>1) printf("%d %d\n",i,i/(i-next[i])); printf("\n"); } return 0; }