POJ1961 Period [KMP应用]

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

#include <string.h>
#include <stdio.h>
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;
}