NC9984E九峰与子序列

Solution

哈希 + DP
复杂度：
首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串[l, r]的部分是否相等。
转移方程：
表示有多少匹配的方案数。
首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串的部分是否相等。
然后暴力枚举转移即可，倒序转移的原理同背包可以节省一维。

坑点：第一次用unsigned long long MLE了，改用unsgined int就过了。

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

/*
    Hash S(s);
    Sometimes we need to use a lot of primes to hash instead of overflow.

    if MLE, try:
        using ull = unisgned int;
*/

struct Hash{
    using ull = unsigned int;
    vector<ull> H, P;
    ull base = 131;
    int n;

    Hash(string s):n((int)s.size()), H((int)s.size() + 1, 0), P((int)s.size() + 1, 0){
        P[0] = 1;
        s = " " + s;
        for (int i = 1; i <= n; i++) {
            H[i] = H[i - 1] * base + s[i] - 'a' + 1;
            P[i] = P[i - 1] * base;
        }
    }

    ull get(int L, int R) {
        return H[R] - H[L - 1] * P[R - L + 1];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;
    Hash S(s);
    int A = s.size();
    vector<ll> f(A + 1);
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        string t;
        cin >> t;
        Hash T(t);
        int B = t.size();
        for (int j = A - B + 1; j >= 1; j--) {
            if (T.get(1, B) == S.get(j, j + B - 1)) {
                f[j + B - 1] += f[j - 1];
            }
        }
    }
    cout << f[A] << '\n';

    return 0;
}