「 HDU P3336 」 Count the string

题目大意

给出一个长度为 $n$ 的字符串 $s$ 要求你求出 $s$ 的每一个前缀在 $s$ 中出现的次数之和。$n\le 200000$。

解题思路

暴力的对每一个前缀进行一次匹配，求出出现次数后求和。

那肯定是不行的，复杂的是 $O(n\times (m+n))$ 的，不用想也知道要 TLE 那我们考虑 $KMP$ 中 $next$ 数组的性质：为每一个前缀的前缀和后缀最长的共同子串的长度。

那这不就是说如果 $next[i] = j$ 的话，那么在 $s$ 中 $1\rightarrow j$ 和 $i-next[i]+1\rightarrow i$ 这两个子串是相等的。同时也代表 $1\rightarrow j$ 这个前缀的出现次数多了 $1$。

这就好办了。我们只需要求出 $s$ 的 $next$ 数组，然后就可以算出前缀的出现次数。但是要注意算出的 $next$ 并不能直接求出出现次数。因为 $next$ 数组存储的是位置。所以要一步一步推过来，很容易就能得到一个递推式 $f[i] = f[nxt[i]]+1$ 到最后统计一遍总和就可以得到答案了。

放上代码

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int maxn = 2e5+, HA = 1e4+;

int T, p, Ans, nxt[maxn], dp[maxn], n;

char s[maxn];

inline void Getnext() {

    for(int i=; i<=n; i++) {

        p = nxt[i-];

        while(p && s[p+] != s[i]) p = nxt[p];

        if(s[p+] == s[i]) nxt[i] = p+;

        else nxt[i] = ;

    }

}

int main() {

    scanf("%d", &T);

    while (T--) {

        memset(nxt, , sizeof(nxt));

        memset(dp, , sizeof(dp));

        Ans = ;

        scanf("%d", &n);

        scanf("%s", s+);

        Getnext();

        dp[] = ;

        for(int i=; i<=n; i++) {

            dp[i] = dp[nxt[i]] + ;

            dp[i] = dp[i] % HA;

        }

        for(int i=; i<=n; i++)

            Ans = (Ans % HA + dp[i] % HA) % HA;

        printf("%d\n", Ans);

    }

}

巴特西

「 HDU P3336 」 Count the string

题目大意

解题思路

放上代码

最新文章

热门文章