Cyclic Nacklace

节省篇幅不粘题面了。。。

看懂题后脑袋里略过KMP,学过但没怎么用过，又直接跳下一题了。。

题意：给定一个字符串，可以从两边加上一些字符使其有循环节。。求最少需要加多少字符。。

思路：补题的时候才发现就是next数组简单应用。用next数组求出自身最大匹配，剩下的即循环节的长度。然后用剩下的长度除去最大匹配中循环节的长度即可。

注：神奇的杭电用next做数组名会CE

（aabaa,abcabca）

const int N=1e5+10;

int t,len,ne[N];

char a[N];

void kmp_pre()

{

    int i=0,j=-1;

    ne[0]=j;

    while(i<len)

    {

        while(j!=-1&&a[i]!=a[j]) j=ne[j];

        ne[++i]=++j;

    }

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",a);

        len=strlen(a);

        kmp_pre();

        int ans=len-ne[len];

        if(len!=ans&&len%ans==0) printf("0\n");

       else printf("%d\n",ans-ne[len]%ans);

    }

    return 0;

}

再次加深对next数组的理解！

巴特西

HDU-3746Cyclic Nacklace，next数组简单应用。

Cyclic Nacklace

最新文章

热门文章