运用next[ ]求周期
求以第i个字符前边字符串的周期
if(i%(i-next[i])==0&&next[i]!=0)则第i个字符前边的串是个轮回串,周期是i/(i-next[i])
#include<stdio.h> #include<string.h> int next[1000010]; char s[1000010]; void get() { int i,j,len; next[1]=0; j=0; len=strlen(s+1); for(i=2;i<=len;i++) { while(j>0&&s[i]!=s[j+1])j=next[j]; if(s[i]==s[j+1]) j++; next[i]=j; } } int main() { int i,j=1,n,len; while(scanf("%d",&n),n) { scanf("%s",s+1); len=strlen(s+1); get(); printf("Test case #%d\n",j++); for(i=2;i<=len;i++) if(i%(i-next[i])==0&&next[i]!=0) printf("%d %d\n",i,i/(i-next[i])); printf("\n"); } return 0; }