Hdu 3336 Count the string (KMP+DP 前缀出现次数和)

本是古典何须时尚 2022-08-27 11:43 7阅读 0赞

题意：给一个字符串，对每一个前缀出现的次数求和。

这里有另外一种思路：[【KMP】HDU 3336 Count the string - KIDxの博客 - ITeye技术网站][KMP_HDU 3336 Count the string - KIDx_ - ITeye]

#include <cstdio>
    #include <cstring>
    
    const int MOD=10007;
    const int N=200005;
    char s[N];
    int next[N],n,f[N];
    
    void getNext(char s[],int len)
    {
        next[0]=-1;
        int i=0,j=-1;
        while (i<len)
        {
            if (j==-1 || s[i]==s[j])
                next[++i]=++j;
            else j=next[j];
        }
    }
    
    int DP ()
    {
        int ans=0;
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++)
        {//f[i]表示长度为i的字符串(也就是把str[i]当成'\0')总共含前缀的数量
            f[i]=f[next[i]]+1;//+1表示长度为next[i]的前缀在当前结尾又出现了一次
            ans=(ans+f[i])%MOD;
        }
        return ans;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            scanf("%s",s);
            getNext(s,n);
            printf("%d\n",DP());
        }
        return 0;
    }

[KMP_HDU 3336 Count the string - KIDx_ - ITeye]: http://972169909-qq-com.iteye.com/blog/1114968

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 [kuangbin带你飞]专题十六 KMP & 扩展KMP & ManacherK - Count the string HDU - 3336(前缀数量问题）...

K - Count the string HDU - 3336 题目链接：[https://vjudge.net/contest/70325\problem/K][htt

た入场券/ 2023年08月17日 15:41/ 0 赞/ 139 阅读

相关 HDU 3336 Count the string（kmp + dp）

Count the string Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

妖狐艹你老母/ 2022年09月30日 03:50/ 0 赞/ 170 阅读

相关 HDU 3336-Count the string

[HDU 3336][] KMP+DP include<cstdio> include<cstring> using namespac

川长思鸟来/ 2022年09月22日 13:52/ 0 赞/ 14 阅读

相关 Hdu 3336 Count the string (KMP+DP 前缀出现次数和)

题意：给一个字符串，对每一个前缀出现的次数求和。这里有另外一种思路：[【KMP】HDU 3336 Count the string - KIDxの博客 - ITeye技术网

本是古典何须时尚/ 2022年08月27日 11:43/ 0 赞/ 8 阅读

相关 Zoj 3587 Marlon's String (KMP 字符串拼接前缀出现次数)

题意：给字符串S，T，找到所有的tetrad (a,b,c,d)， Sa..b + Sc..d = T , a≤b and c≤d.也就是把T分成两段，这两段都由S中的子串组成

红太狼/ 2022年08月23日 12:58/ 0 赞/ 8 阅读

相关 HDU 3336 Count the string（KMP+稍微DP+next数组的运用）

It is well known that AekdyCoin is good at string problems as well as number theory prob

喜欢ヅ旅行/ 2022年06月10日 14:22/ 0 赞/ 154 阅读

相关 HDU 6208 The Dominator of Strings（stl）

The Dominator of Strings Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/3

超、凢脫俗/ 2022年06月08日 07:57/ 0 赞/ 152 阅读

相关 Hdu 3336 Count the string(kmp&&dp+kmp)

[传送门][Link 1] 题意：给你一个长度为 n 的字符串(1 <= n <= 200000)，输出所有前缀出现的次数之和，然后mod10007的结果。分析：如果我们

冷不防/ 2022年05月19日 07:17/ 0 赞/ 176 阅读

相关 B - Count the string（统计字符串）

题目描述： It is well known that AekdyCoin is good at string problems as well as number th

Bertha 。/ 2022年03月19日 05:43/ 0 赞/ 249 阅读

相关 HDU6470 Count

好久没写矩阵快速幂（其实这题可以直接用杜教的BM板子，比赛时突然想练一下矩阵快速幂）比较难搞的是 n 3 n^3 n3 考虑 n 3 − > ( n + 1 ) 3

向右看齐/ 2021年09月18日 12:36/ 0 赞/ 288 阅读