即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Cyclic Nacklace (kmp里next数组的运用)

编程语言 duan_1998 15℃ 0评论

【题目来源】https://vjudge.net/problem/HDU-3746


【题意】


题意是给出一个字符串,要求变成一个周期串,最少需要几个字符?


【思路】


也不知道怎地,想到了next数组,数组里记录的数字可以看成是一个周期。


举例说明:


字符串abcabcabc


next数组:0 0 0 1 2 3 4 5 6


而字符串abcabc


next数组:0 0 0 1 2 3


因为有大于0的数字的说明前面有重复的,并且,若是连续出现这样的会数字,说明一直连续,那不就是周期串了吗。。只需要字符总个数减去最后一位的next值,就可以得到最小循环周期,当然,可能会想这样的例子:


abcabcabcaca


0 0 0 1 2 3 4 5 6 7 0 1


那么这个字符串的最小周期是几呢?


答案是11。


【代码】

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod=1e9+7;
const double esp=1e-5;
typedef unsigned long long ll;
typedef long long LL;
char s[100000+10];
int ne[100000+10];
int n,maxx;
void get_next()
{
    int i=0,j;
    j=ne[0]=-1;
    while(iwhile(-1!=j&&s[i]!=s[j]) j=ne[j];
        ne[++i]=++j;
    }
}
int main()
{
    int T;
    scanf("%d%*c",&T);
    while(T--)
    {
        scanf("%s",s);
        n=strlen(s);
        get_next();
//        for(int i=1;i<=n;i++)
//        {
//            cout<
//        }
//        cout<
        int ans=n-ne[n];
//        cout<<"ans="<
        if(ans==0)
            printf("0\n");
        else if(ne[n]!=0&&n%ans==0)
            printf("0\n");
        else
            printf("%d\n",ans-n%ans);
    }
}

转载请注明:CodingBlog » Cyclic Nacklace (kmp里next数组的运用)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情