题目大意：输出字符串所有前缀的循环节个数，下标从1开始，i 和1-i循环节的个数
题解：网上摘得
KMP最小循环节、循环周期：
定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。
（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1000009 using namespace std; int n,len; char s[N]; int nxt[N]; void getnext() { memset(nxt,0,sizeof(nxt)); for(int i=2,j=0;i<=len;i++) { while(s[i]!=s[j+1]&&j) j=nxt[j]; if(s[i]==s[j+1]) nxt[i]=++j; } } int main() { while(1) { scanf("%d",&len); if(!len) break; scanf("%s",s+1); getnext(); cout<<"Test case #"<<++n<<endl; for(int i=1;i<=len;i++) { int k=i-nxt[i]; if(i!=k&&i%k==0) printf("%d %d\n",i,i/k); } printf("\n"); } return 0; }
原文：https://www.cnblogs.com/zzyh/p/12005425.html