文本生成器

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2415 字
AC 自动机上 DP 统计安全串正难则反
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1485
// 题意：给 N 个大写单词和长度 M，求长度为 M、至少包含一个所给单词的大写字符串有多少个，答案对 10007 取模。
// 思路：单词建 AC 自动机并标出危险状态，用 DP 统计「长度为 i 且未碰到任何单词、停在状态 u」的串数，正难则反，答案 = 26^M - 所有安全状态的数量之和。
// 复杂度：O(M × 状态数 × 26) 时间 / O(状态数) 空间
// 易错点：危险标记要沿 fail 链传递，只标自己的结尾会漏掉「后缀是单词」的状态，导致多算安全串。
// 易错点：答案是 26^M 减去安全串数，取模后可能为负，要加 MOD 再取模。
#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
struct Node {
    int ch[26];
    int fail;
    bool bad;
    Node(){
        memset(ch, 0, sizeof(ch));
        fail = 0;
        bad = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;
    vector<Node> tr;
    tr.reserve(6000 + 5);
    tr.push_back(Node());
    for(int i = 0; i < N; i++){
        string w;
        cin >> w;
        int u = 0;
        for(int j = 0; j < (int)w.size(); j++){
            int c = w[j] - 'A';
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
        }
        tr[u].bad = true;
    }
    queue<int> q;
    for(int c = 0; c < 26; c++){
        if(tr[0].ch[c]) q.push(tr[0].ch[c]);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(tr[tr[u].fail].bad) tr[u].bad = true;
        for(int c = 0; c < 26; c++){
            int v = tr[u].ch[c];
            if(v){
                tr[v].fail = tr[tr[u].fail].ch[c];
                q.push(v);
            }else{
                tr[u].ch[c] = tr[tr[u].fail].ch[c];
            }
        }
    }
    int sz = (int)tr.size();
    vector<int> dp(sz, 0), ndp(sz, 0);
    dp[0] = 1;
    for(int i = 0; i < M; i++){
        fill(ndp.begin(), ndp.end(), 0);
        for(int u = 0; u < sz; u++){
            if(!dp[u] || tr[u].bad) continue;
            for(int c = 0; c < 26; c++){
                int v = tr[u].ch[c];
                if(tr[v].bad) continue;
                ndp[v] += dp[u];
                if(ndp[v] >= MOD) ndp[v] -= MOD;
            }
        }
        dp.swap(ndp);
    }
    int safe = 0;
    for(int u = 0; u < sz; u++){
        if(!tr[u].bad){
            safe += dp[u];
            if(safe >= MOD) safe -= MOD;
        }
    }
    int total = 1;
    for(int i = 0; i < M; i++) total = total * 26 % MOD;
    int ans = (total - safe) % MOD;
    if(ans < 0) ans += MOD;
    cout << ans << "\n";
    return 0;
}
文本生成器

正文

一本通·提高篇的其它内容
