BZOJ1030 文本生成器（AC自动机+DP）

求长度为(m)的包含至少一个模式串的字符串数量

---

考虑长度为(m)的不包含任何模式串的字符串数量
(dp[i][j])表示当前长度为(i)，匹配到(Trie)的(j)节点的答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6010;
const int mod = 1e4 + 7;
int n, m;
int bin(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = (ll)x * x % mod)
        if (y & 1) ans = (ll)ans * x, ans %= mod;
    return ans;
}
struct Trie {
    int next[maxn][26], fail[maxn], end[maxn];
    int last[maxn];
    int dp[110][maxn];
    int root, L;
    int newnode() {
        for (int i = 0; i < 26; i++)
            next[L][i] = -1;
        fail[L] = last[L] = end[L] = 0;
        return L++;
    }
    void init() {
        L = 0;
        root = newnode();
    }
    void insert(char buf[]) {
        int len = strlen(buf);
        int now = root;
        for (int i = 0; i < len; i++) {
            if (next[now][buf[i] - 'A'] == -1)
                next[now][buf[i] - 'A'] = newnode();
            now = next[now][buf[i] - 'A'];
        }
        end[now]++;
    }
    void build() {
        queue<int> Q;
        fail[root] = root;
        for (int i = 0; i < 26; i++) {
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                Q.push(next[root][i]);
            }
        }
        while (!Q.empty()) {
            int now = Q.front();
            Q.pop();
            end[now] += end[fail[now]];
            for (int i = 0; i < 26; i++) {
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    int son = next[now][i];
                    fail[son] = next[fail[now]][i];
                    last[son] = end[fail[son]] ? fail[son] : last[fail[son]];
                    Q.push(next[now][i]);
                }
            }
        }
    }
    void solve() {
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < L; j++) {
                for (int k = 0; k < 26; k++) {
                    if (end[next[j][k]]) continue;
                    dp[i][next[j][k]] += dp[i - 1][j];
                    dp[i][next[j][k]] %= mod;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < L; i++) {
            ans += dp[m][i];
            ans %= mod;
        }
        printf("%d
", ((bin(26, m) - ans) % mod + mod) % mod);
    }
} ac;
char s[maxn];
int main() {
    ac.init();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        ac.insert(s);
    }
    ac.build();
    ac.solve();
    return 0;
}