hdu1358 KMP

求循环节。

#include<stdio.h>
#include<string.h>
#define maxn 1000010
int next[maxn];
char s[maxn];
void getnext()
{
    int j,k,len=strlen(s);
    j=0;
    k=-1;
    next[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}
int main()
{
    int i,len,ff=0;
    while(scanf("%d",&len)!=EOF)
    {
        if(len==0)
            break;
        scanf("%s",s);
        getnext();
        printf("Test case #%d
",++ff);
    /*    for(i=1;i<=len;i++)
            printf("%d ",next[i]);
        printf("
");*/
        for(i=2;i<=len;i++)
        {
            if(i%(i-next[i])==0&&i!=(i-next[i]))
            {
                printf("%d %d
",i,i/(i-next[i]));
            }
        }
        printf("
");
    }
}