HDU3336 Count the string 题解 KMP算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3336

题目大意：找出字符串s中和s的前缀相同的所有子串的个数。

题目分析：KMP模板题。这道题考虑 nxt[] 数组的应用。以 s[i] 结尾的子串中一共有多少个子串可以作为s的前缀呢？我们只要令 t = nxt[i]，cnt=0

每当 t!=-1，cnt++, t=nxt[t] 就可以了。

当然，我们可以用dp优化，dp[i] = dp[nxt[i]]+1 ，当然，如果 nxt[i]==-1 ，那么 dp[i] 就是 1，因为 s[0...i] 。

实现代码如下：

#include <cstdio>

#include <string>

#include <iostream>

using namespace std;

#define MOD 10007

const int maxn = 1001000;

int T, m, nxt[maxn], ans, f[maxn];

string t;

void cal_next() {

    m = t.length();

    for (int i = 0, j = -1; i < m; i ++) {

        while (j != -1 && t[j+1] != t[i]) j = nxt[j];

        nxt[i] = (j+1 < i && t[j+1] == t[i]) ? ++j : -1;

    }

}

void solve() {

    ans = 0;

    for (int i = 0; i < m; i ++) {

        if (nxt[i] == -1) f[i] = 1;

        else f[i] = f[nxt[i]] + 1;

        ans = (ans + f[i]) % MOD;

    }

    cout << ans << endl;

}

int main() {

    scanf("%d", &T);

    while (T --) {

        cin >> m >> t;

        cal_next();

        solve();

    }

    return 0;

}

作者：zifeiy

巴特西

HDU3336 Count the string 题解 KMP算法

最新文章

热门文章