首页 > 其他 > 详细

HDU 3336 Count the string

时间:2018-06-02 16:08:18      阅读:202      评论:0      收藏:0      [点我收藏+]

题意:字符串的每个前缀在原字符串中出现的次数和

思路:我们求出字符串的next数组,对于每个前缀,最少有一个,然后对于每个位置我们看他的next数组值是否大于0,如果大于0,ans++

代码:(有点看不懂网上得到通解)

#include <cstdio>
#include <cstring>
const int maxn=2e5+7;
const int MOD=10007;
char a[maxn];
int len;
int next[maxn];

void getNext(char T[])
{
    int j, k;
    j = 0;
    k = -1;
    next[0] = -1;
    while(j < len)
        if(k == -1 || T[j] == T[k])
            next[++j] = ++k;
        else
            k = next[k];
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&len);
        scanf("%s",a);
        memset(next,0,sizeof(next));
        getNext(a);
//        for(int i=0;i<=len;i++){
//            printf("%d ",next[i]);
//        }
//        puts("");
        int ans=len%MOD;
        for(int i=1;i<=len;i++){
            if(next[i]>0)ans++;
            ans%=MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

HDU 3336 Count the string

原文:https://www.cnblogs.com/lalalatianlalu/p/9125640.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!