单词

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2057 字
AC 自动机计数沿 fail 链逆序累加
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1482
// 题意：给 N 个单词（论文即由这些单词组成），求每个单词在所有单词拼接出的文章中作为子串出现了多少次。
// 思路：单词建 AC 自动机，把每个单词的每个前缀结点计数加一；再按 BFS 逆序把每个结点的计数累加到它的 fail 父结点上，此时单词结尾结点的计数就是它在全文中的出现次数。
// 复杂度：O(所有单词总长 × 26) 时间 / O(所有单词总长 × 26) 空间
// 易错点：必须保留 Trie 的原始边来逐个单词走，不能像常规做法那样把 ch 直接回填成完全转移后再统计。
// 易错点：计数要按 BFS 逆序（深度从大到小）向 fail 父结点累加，顺序反了会漏掉长单词对短单词的贡献。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    int fail;
    long long cnt;
    Node(){
        memset(ch, 0, sizeof(ch));
        fail = 0;
        cnt = 0;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<string> w(n);
    int total = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i];
        total += (int)w[i].size();
    }
    vector<Node> tr;
    tr.reserve(total + 1);
    tr.push_back(Node());
    vector<int> endNode(n, 0);
    for(int i = 0; i < n; i++){
        int u = 0;
        for(int j = 0; j < (int)w[i].size(); j++){
            int c = w[i][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].cnt++;
        }
        endNode[i] = u;
    }
    vector<int> order;
    order.reserve(tr.size());
    queue<int> q;
    for(int c = 0; c < 26; c++){
        if(tr[0].ch[c]){
            q.push(tr[0].ch[c]);
            order.push_back(tr[0].ch[c]);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int c = 0; c < 26; c++){
            int v = tr[u].ch[c];
            if(!v) continue;
            int f = tr[u].fail;
            while(f && !tr[f].ch[c]) f = tr[f].fail;
            tr[v].fail = tr[f].ch[c];
            q.push(v);
            order.push_back(v);
        }
    }
    for(int i = (int)order.size() - 1; i >= 0; i--){
        int u = order[i];
        tr[tr[u].fail].cnt += tr[u].cnt;
    }
    for(int i = 0; i < n; i++){
        cout << tr[endNode[i]].cnt << "\n";
    }
    return 0;
}
单词

正文

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