Censoring (Gold)（AC自动机多字符串匹配+栈）

Censoring (Gold)

题意：给了一段文本串，再给了含 $N$N个字符串的字典。将文本从左到右，如果遇到了字典中的字符串，则删去这一段文本，继续按顺序匹配，输出最终文本剩下的内容。

思路：

1. 用字典建立好AC自动机，处理出每个节点所能代表的字典中的最长字符串的长度（用topo排序处理）
2. 将文本串在AC自动机上跑，并将每次的节点放到栈里面；如果匹配成功了，则在栈中弹出此长度的个数，并且指针移动到新的top在AC自动机上的pos

题目描述

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define rt 1,n,1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn], t[maxn];
int trie[maxn][26], fail[maxn];
int pos[maxn], stk[maxn], ed[maxn], in[maxn];
int tot, top;
vector<int> refail[maxn];

void insert() {
    int len=strlen(t), p=0;
    for(int i=0; i<len; ++i) {
        int k=t[i]-'a';
        if(!trie[p][k]) trie[p][k]=++tot;
        p=trie[p][k];
    }
    ed[p]=len;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                in[trie[now][i]]++;
                refail[trie[now][i]].pb(trie[fail[now]][i]);
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

void topo() {
    queue<int> q;
    for(int i=0; i<=tot; ++i) if(!in[i]) q.push(i);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(auto p: refail[now]) {
            ed[p]=max(ed[p],ed[now]);
            if(--in[p]==0) q.push(p);
        }
    }
}

void solve() {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        stk[++top]=i;
        int k=s[i]-'a';
        p=trie[p][k];
        if(ed[p]) top-=ed[p], p=pos[stk[top]];
        pos[stk[top]]=p;
    }
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    scanf("%s", s);
    int N=read();
    for(int i=0; i<N; ++i) scanf("%s", t), insert();
    build();
    solve();
    for(int i=1; i<=top; ++i) putchar(s[stk[i]]);
    puts("");
}