考察对KMP的next数组的掌握,next数组也就是失败指针指向它失败后应该指向的位置,next[i]~i之间就是一个循环节，所以只要满足i%(i-next[i])==0即可。

#include 
     
      #include 
      
       int cas=1,n;char s[1000005];int next[1000005];void solve(){    next[1]=0;    int len=strlen(s+1);    for(int i=2,j=0;i<=len;i++){        while(j>0&&s[i]!=s[j+1])j=next[j];        if(s[i]==s[j+1])j++;        next[i]=j;        if(i%(i-next[i])==0&&i/(i-next[i])!=1){            printf("%d %d\n",i,i/(i-next[i]));        }    }}int main(){//freopen("test.in","r",stdin);    while(scanf("%d",&n),n){        scanf("%s",s+1);        printf("Test case #%d\n",cas++);        solve();        printf("\n");    }    return 0;}