Keywords Search

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2482 字
AC 自动机扫文章，fail 树统计命中
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1479
// 题意：T 组数据，每组给 n 个待查单词和一篇文章，问这篇文章里出现了多少个不同的待查单词。
// 思路：单词建 Trie 并求 fail，扫描文章时只标记到达的状态；一个单词被命中当且仅当它的结尾结点在某个被标记状态的 fail 链上，即该结尾结点的 fail 子树里有标记，故沿 fail 树自底向上把标记或上去即可统计。
// 复杂度：O(单词总长 + 文章长度) 时间 / O(单词总长 × 26) 空间
// 易错点：统计的是「出现了多少个不同的单词」，同一单词出现多次只算一次，不能简单地累加出现次数。
// 易错点：多组数据要整棵 Trie 重建，只把结点数置 0 会残留上一组的 ch 和 fail。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    int fail;
    bool ed;
    Node(){
        memset(ch, 0, sizeof(ch));
        fail = 0;
        ed = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int n;
        cin >> n;
        vector<Node> tr;
        tr.reserve(n * 50 + 1);
        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].ed = true;
        }
        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);
            }
        }
        string s;
        cin >> s;
        int sz = (int)tr.size();
        vector<char> hit(sz, 0);
        int u = 0;
        for(int i = 0; i < (int)s.size(); i++){
            int c = s[i] - 'a';
            while(u && !tr[u].ch[c]) u = tr[u].fail;
            u = tr[u].ch[c];
            hit[u] = 1;
        }
        for(int i = sz - 1; i >= 0; i--){
            int v = order[i];
            if(hit[v]) hit[tr[v].fail] = 1;
        }
        int ans = 0;
        for(int i = 1; i < sz; i++){
            if(tr[i].ed && hit[i]) ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}
Keywords Search

正文

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