poj2406 KMP

kmp简单题 找循环节。由于KMP的next[]数组，所以可以考虑最后一组的情况，及next[n]的值；n-next[n]的值表示一个循环节。

如果n%(n-next[n])!=0表明该循环不成立。不然就是直接得到。

#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];
        }
    }
}
void getans()
{
    int ans,flen;
    int n=strlen(s);
    flen=n-next[n];
    if(n%flen==0)
        printf("%d
",n/flen);
    else printf("1
");
}
int main()
{
    while(scanf("%s",s)!=EOF)
    {
        if(s[0]=='.')break;
        getnext();
        getans();
    }
}