看题传送门：

给定一个长度为n的循环节，求它的每个前缀的最短循环节。换句话说,对于每个i （2<=i<=n），求一个最大的整数K>1（如果k处在），使得s的前i个字符组成的前缀是某个字符串重复K次得到。输出所有存在K的i对应的K。

比如aabaabaabaab只有当 i=2 6 9 12时k存在，且分别为2,2,3,4

分析：

用KMP求得失配函数f为

j: 0  1  2  3  4  5  6  7  8  9  10  11  12

P a  a  b  a  a  b  a  a  b  a    a   b 

f 0  0  1  0  1   2  3  4  5  6    7  8    9

可以看出，如果它是一个循环节，那么有 i%(i-f[i])==0

为什么会这样？

KMP原来是模板串和文本串之间的匹配关系，而失配函数是模板串自身（将自身平移f[i]，看是否能匹配）这题省略了文本串，可将文本串看做模板串，错位的部分即为i-f[i]，如果这i 个组成循环节，那么 i - f[i]这部分必然也是循环节。

为什么这样？下面摘自

-----------------------

-----------------------

 k    m        x      j       i

由上，next【i】=j，两段红色的字符串相等（两个字符串完全相等），s[k....j]==s[m....i]

设s[x...j]=s[j....i](xj=ji)

则可得，以下简写字符串表达方式

kj=kx+xj;

mi=mj+ji;

因为xj=ji，所以kx=mj，如下图所示

 

-------------

      -------------

 k   m        x     j   

看到了没，此时又重复上面的模型了，kx=mj，所以可以一直这样递推下去

所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);

#include
    
     const int MAXN=1000000+10;char p[MAXN];int f[MAXN];void getfail(const int &n){	f[0]=f[1]=0;	for(int i=1;i
     
       0 && p[i]!=p[j]) j=f[j];		if(p[i]==p[j]) j++;		f[i+1]=j;	}}int main(){	int n;	int kase=1;	while(scanf("%d",&n),n)	{		scanf("%s",p);		getfail(n);		printf("Test case #%d\n",kase++);				/*		for(int i=0;i
      
       0 && i%(i-f[i])==0)				printf("%d %d\n",i,i/(i-f[i]));		}		printf("\n");	}}