hdu3746 KMP

这题琢磨了挺长的时间。需要理解next[]表示了什么; next[i]代表了前缀和后缀的最大匹配的值，也就是个数。

len-next[len]表示循环节的长度; 比如abcab   int fl=len-next[len]=3;循环节长度为3,即cab。然后int len=strlen(s)=5；

如果len%fl==0,那就count=len/fl,不然count=len/fl+1;count表示根据长度能够循环的次数。count*fl表示能够满足循环的时候的长度，

count*fl-len就是缺少的长度。不过如果next[len]==0，也就是本身的时候，就要输出自己的len了；

#include<stdio.h>
#include<string.h>
#define maxn 100010
char c[maxn];
int next[maxn];
void getnext()
{
    int j,k,len=strlen(c);
    j=0;
    k=-1;
    next[0]=-1;
    while(j<len)
    {
        if(k==-1||c[j]==c[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}
void kmp()
{
    int i,j;
    getnext();
    int len=strlen(c);

    /*for(i=0;i<=len;i++)
        printf("%d   ",next[i]);
    printf("
");*/
    int fl=len-next[len];//循环节长度
    int count=0;
    i=len;
    count=len/fl;//循环节的次数
    if(len%fl)//如果不能整除就要+1
        count++;
//    printf("%d  %d  ",fl,count);
    if(next[len]==0)//如果直接为0 所以就本身长度
        printf("%d
",len);
    else
        printf("%d
",count*fl-len);
    
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",c);
        kmp();
    }
}