Censoring

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1930 字
AC自动机配栈，匹配成功即弹出
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1470
// 题意：给串 S 和 n 个屏蔽词，从头反复删除最先出现的屏蔽词（删后可能产生新屏蔽词），输出最终的 S。
// 思路：屏蔽词建 AC 自动机，扫描 S 时把字符与自动机状态一起压栈，一旦命中词尾就弹出该词长度个字符与状态，自动接续匹配。
// 复杂度：O(|S|+∑|t_i|) 时间 / O(∑|t_i|) 空间
// 易错点：栈里必须同时存状态，弹出后要用栈顶状态继续匹配才能处理删除后新产生的屏蔽词；不能只删一次后从头重扫。
#include <bits/stdc++.h>
using namespace std;
struct Node{
    int ch[26];
    int fail;
    int endlen;
    Node(){
        memset(ch,0,sizeof(ch));
        fail=0;
        endlen=0;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S;
    if(!(cin>>S)) return 0;
    int n;
    if(!(cin>>n)) return 0;
    vector<Node> tr(1);
    for(int i=0;i<n;i++){
        string t;
        if(!(cin>>t)) return 0;
        int u=0;
        for(int c=0;c<(int)t.size();c++){
            int x=t[c]-'a';
            if(!tr[u].ch[x]){
                tr[u].ch[x]=(int)tr.size();
                tr.push_back(Node());
            }
            u=tr[u].ch[x];
        }
        tr[u].endlen=(int)t.size();
    }
    vector<int> que;
    que.reserve(tr.size());
    for(int x=0;x<26;x++){
        if(tr[0].ch[x]) que.push_back(tr[0].ch[x]);
    }
    for(size_t h=0;h<que.size();h++){
        int u=que[h];
        for(int x=0;x<26;x++){
            int v=tr[u].ch[x];
            if(v){
                tr[v].fail=tr[tr[u].fail].ch[x];
                que.push_back(v);
            }else{
                tr[u].ch[x]=tr[tr[u].fail].ch[x];
            }
        }
    }
    string out;
    vector<int> st;
    out.reserve(S.size());
    st.reserve(S.size()+1);
    st.push_back(0);
    for(int i=0;i<(int)S.size();i++){
        int x=S[i]-'a';
        int u=tr[st.back()].ch[x];
        out.push_back(S[i]);
        st.push_back(u);
        if(tr[u].endlen){
            int L=tr[u].endlen;
            for(int j=0;j<L;j++){
                out.pop_back();
                st.pop_back();
            }
        }
    }
    cout<<out<<'\n';
    return 0;
}
Censoring

正文

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