欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-02 17:33:22
...

传送门

题意:给你一个长度为 n 的字符串(1 <= n <= 200000),输出所有前缀出现的次数之和,然后mod10007的结果。

分析:如果我们要把字符串的每一个前缀都拿去和字符串进行匹配的话,那么复杂度就是O(n),很明显是会TLE的,所以我们考虑其他方法。

方法一:Next[j] = x 代表的是前j个字符中前缀和后缀的最大匹配长度是x,所以我们直接根据Next数组去枚举 j 从 n ->1每个前缀出现的次数,这里需要注意的是在求sum的时候每一步都有可能超出范围,所以每求一次sum就取模一次。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
const int mod = 10007;
int T,N;
char s[maxn];
int Next[maxn];

void getNext()
{
    int j = -1, i = 0;
    Next[0] = -1;
    while(i<N)
    {
        if(j==-1||s[i]==s[j])
        {
            i++;
            j++;
            Next[i]=j;
        }
        else j = Next[j];
    }
}

void slove()
{
    int sum = 0;
    for(int i=N;i>=1;i--)
    {
        sum=(sum+1)%mod;
        int j = Next[i];
        while(j){
            sum=(sum+1)%mod;
            j=Next[j];
        }
    }
    printf("%d\n",sum);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        scanf("%s",s);
        getNext();
        slove();
    }
    return 0;
}

 

方法二:出现的次数是因为字符的不断增加而增加的,我们想到用dp来递推求解,dp[i]表示的是前i个字符构成的前缀所出现的次数,再利用next数组根据前后缀所匹配的情况,根据之前已出现过的字符的次数,来递推现在新增字符后的次数,这里不是很好理解,大家可以自行模拟一遍。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
const int mod = 10007;
int T,N;
char s[maxn];
int Next[maxn];
int dp[maxn];/**dp[i]为前i个字符组成的前缀出现的次数*/

void getNext()
{
    int j = -1, i = 0;
    Next[0] = -1;
    while(i<N)
    {
        if(j==-1||s[i]==s[j])
        {
            i++;
            j++;
            Next[i]=j;
        }
        else j = Next[j];
    }
}

void slove()
{
    int sum = 0;
    for(int i=1;i<=N;i++)
    {
        dp[i]=(dp[Next[i]]+1)%mod;
        sum=(sum+dp[i])%mod;
    }
    printf("%d\n",sum);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        scanf("%s",s);
        getNext();
        slove();
    }
    return 0;
}

 

相关标签: Hdu Next数组