Censoring

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2269 字
AC 自动机配状态栈实现删除后回退
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1481
// 题意：给字符串 S 和 n 个屏蔽词，从左往右扫描 S，每发现一个屏蔽词就把它删掉并从开头重新扫描，输出最终剩下的串。
// 思路：屏蔽词建 AC 自动机，扫描 S 时把字符和当前状态一起压栈；一旦当前状态匹配了某个屏蔽词，就从栈里弹出该词长度的结点，相当于把这段删除后继续往后扫。
// 复杂度：O(|S| + 屏蔽词总长) 时间 / O(|S| + 屏蔽词总长 × 26) 空间
// 易错点：删除后可能拼出新的屏蔽词，靠「状态栈」回退即可自动处理，不能只做一次字符串替换。
// 易错点：每个状态要沿 fail 链取最长匹配长度，只判断自己是不是结尾会漏掉作为后缀命中的更长的屏蔽词。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    int fail;
    int matchLen;
    Node(){
        memset(ch, 0, sizeof(ch));
        fail = 0;
        matchLen = 0;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if(!(cin >> s)) return 0;
    int n;
    cin >> n;
    vector<Node> tr;
    tr.reserve(100000 + 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].matchLen = (int)w.size();
    }
    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].matchLen > tr[u].matchLen) tr[u].matchLen = tr[tr[u].fail].matchLen;
        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];
            }
        }
    }
    vector<int> st;
    vector<char> stc;
    st.reserve(s.size() + 1);
    stc.reserve(s.size() + 1);
    st.push_back(0);
    int u = 0;
    for(int i = 0; i < (int)s.size(); i++){
        int c = s[i] - 'a';
        u = tr[u].ch[c];
        st.push_back(u);
        stc.push_back(s[i]);
        if(tr[u].matchLen){
            int k = tr[u].matchLen;
            for(int j = 0; j < k; j++){
                st.pop_back();
                stc.pop_back();
            }
            u = st.back();
        }
    }
    for(size_t i = 0; i < stc.size(); i++) cout << stc[i];
    cout << "\n";
    return 0;
}
Censoring

正文

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