P3121 [USACO15FEB]审查（黄金）Censoring (Gold) （银的正解是KMP）
AC自动机+栈
多字符串匹配--->AC自动机
删除单词的特性--->栈
所以我们先打个AC自动机模板
然后搞2个栈维护：
- AC自动机目前跑到字典树上的哪个点
- 已经跑过且没被删除的字符（答案栈）
每次碰到有结尾标记的点，就让2个栈弹出这个点所对应的单词的长度
最后输出第二个栈就行了
attention：输出答案后要换行，否则会蜜汁爆炸7pts
P3121 code（P4824要稍作修改）：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct data{
int nxt[],fail/*,last*/,end;
}a[];
int n,cnt,top,stk1[],stk2[];
char g[],q[];
inline void Trie_build(){
scanf("%s",q);
int u=,len=strlen(q);
for(int i=;i<len;++i){
int p=q[i]-'a';
if(!a[u].nxt[p]) a[u].nxt[p]=++cnt;
u=a[u].nxt[p];
}a[u].end=len;
}
void AC_build(){
queue <int> h;
for(int i=;i<;++i) if(a[].nxt[i]) h.push(a[].nxt[i]);
while(!h.empty()){
int x=h.front(); h.pop();
for(int i=;i<;++i){
int &to=a[x].nxt[i];
if(to){
a[to].fail=a[a[x].fail].nxt[i];
//a[to].last= a[a[to].fail].end ? a[to].fail:a[a[to].fail].last;
h.push(to);
}else to=a[a[x].fail].nxt[i];
}
}
}
//---------以上裸AC自动机------------
void query(){
int u=,len=strlen(g);
for(int i=;i<len;++i){
u=a[u].nxt[g[i]-'a'];
stk1[++top]=u; //栈1存当前点在字典树中的位置
stk2[top]=i; //栈2存字符（答案）在主串中所在的位置
while(a[u].end) top-=a[u].end,u= top ? stk1[top]:; //删除操作
}
for(int i=;i<=top;++i) putchar(g[stk2[i]]);
putchar('\n'); //不换行就蜜汁爆炸（大雾）
}
int main(){
scanf("%s",g); scanf("%d",&n);
for(int i=;i<=n;++i) Trie_build();
AC_build();
query();
return ;
}