call 大佬 help7——kmp 补齐 循环节

http://acm.hdu.edu.cn/showproblem.php?pid=3746

用kmp算法，那么

但是也等于上面的是正确的

也等于下面是错误的

why？

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int n,t;

char s[];

int f[];

void getnext()

{

    for(int i=;i<n;i++)

    {

        int j=f[i];

        while(j&&s[i]!=s[j]) j=f[j];

        f[i+]= s[i]==s[j] ? j+:;

    }

}

int main()

{

        scanf("%d",&t);

        while(t--)

        {

            scanf("%s",s);

            n=strlen(s);

            memset(f,,sizeof(f));

            getnext();

            if(f[n]==) printf("%d\n",n);

            else if(n%(n-f[n])==) printf("0\n");

            else

            {

                int a=n-f[n];

                printf("%d\n",a-n%a);

            }

        }

}

正确的

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int n,t;

char s[];

int f[];

void getnext()

{

    for(int i=;i<n;i++)

    {

        int j=f[i];

        while(j&&s[i]!=s[j]) j=f[j];

        f[i+]= s[i]==s[j] ? j+:;

    }

}

int main()

{

        scanf("%d",&t);

        while(t--)

        {

            scanf("%s",s);

            n=strlen(s);

            memset(f,,sizeof(f));

            getnext();

            if(f[n]==) printf("%d\n",n);

            else if(n%(n-f[n])==) printf("0\n");

            else

            {

                if(f[n]<=n/) printf("%d\n",n-f[n]*);

                else printf("%d\n",*n-*f[n]);

            }

        }

}

错误的