题意：
一个字符串，求所有循环节长度及位置
3
aaa
12
aabaabaabaab
0
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
通过样例1再解释下题意：
aa可由第1个a循环 2 次得到，输出位置：2，循环长度：2
aaa可由第1个a循环 3 次得到，输出位置：3，长度：3
做法：KMP的 next 预处理
#include<stdio.h> #include<string.h> using namespace std; const int mxn=1e6+10; int n,cnt,next[mxn]; char str[mxn]; void Sol() { int j=0; for(int i=2;i<=n;++i) { while(j>0 && str[i]!=str[j+1]) j=next[j]; if(str[i]==str[j+1]) ++j; next[i]=j; } } int main() { while(scanf("%d",&n) && n) { scanf("%s",str+1); Sol(); printf("Test case #%d\n",++cnt); for(int i=2;i<=n;++i) { int len=i-next[i]; if(i!=len && i%len==0) { printf("%d %d\n",i,i/len); } } puts(""); } return 0; } /* 12 aabaabaabaab 3 aaa 0 */
原文：https://www.cnblogs.com/qseer/p/9926333.html