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=;

    k=-;

    next[]=-;

    while(j<len)

    {

        if(k==-||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("\n");*/

    int fl=len-next[len];//循环节长度

    int count=;

    i=len;

    count=len/fl;//循环节的次数

    if(len%fl)//如果不能整除就要+1

        count++;

//    printf("%d  %d  ",fl,count);

    if(next[len]==)//如果直接为0 所以就本身长度

        printf("%d\n",len);

    else

        printf("%d\n",count*fl-len);

}

int main()

{

    int i,j,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",c);

        kmp();

    }

}

巴特西

hdu3746 KMP

最新文章

热门文章