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

冷不防 2022-05-19 07:17 150阅读 0赞

[传送门][Link 1]

题意：给你一个长度为 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;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3336