P3121 [USACO15FEB] Censoring G
大意
给若干个模式串，和一个文本串，按从前到后的顺序，如果出现一个模式串就删除，注意删除后拼接处可能再出现模式串。
思路
一道好题？
首先是，我们发现是一个文本串和多个模式串的匹配，先想到要用 AC 自动机去解决这个问题，我们先把这些模式串用 AC 自动机构建好，然后我们考虑这样的问题，如何确定是否需要删除串，删除多长。
我们需要用两个 stack 去存贮，一个用来存储最终的答案，一个用来存储状态，不然删完你就不知道原来你在 AC 自动机上走到哪个地方了。
只需要在插入字符串的时候做一些手脚，在结束的位置把答案记一下。
代码
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;const int MAXN = 1e5 + 5;
int ch[MAXN][26], idx = 0;
int fail[MAXN], id[MAXN];
int bad[MAXN];
char c[MAXN], s[MAXN];void Insert(char *q){int now = 0;for(int i = 0;q[i];i ++){int x = q[i] - 'a';if(!ch[now][x]){ch[now][x] = ++ idx;}now = ch[now][x];}bad[now] = strlen(q);
// cout << now << ": " << bad[now] << '\n';
}void build(){queue<int> q;for(int i = 0;i < 26;i ++){if(ch[0][i]) q.push(ch[0][i]);}while(!q.empty()){int u = q.front(); q.pop();for(int i = 0;i < 26;i ++){if(ch[u][i]){fail[ch[u][i]] = ch[fail[u]][i];q.push(ch[u][i]);}else{ch[u][i] = ch[fail[u]][i];}}}
}int main(){// freopen("farmerjohn.in", "r", stdin);// freopen("farmerjohn.out", "w", stdout);int n;cin >> s;cin >> n;for (int i = 1;i <= n;i ++){cin >> c;Insert(c);}build();vector<char> res;vector<int> st;int now = 0;st.push_back(0);for(int i = 0;s[i];i ++){int x = s[i] - 'a';now = ch[now][x];res.push_back(s[i]);st.push_back(now);
// cout << now << '\n';if(bad[now]){
// cout << "hhh\n";int ct = bad[now];for(int i = 0;i < ct;i ++){res.pop_back();st.pop_back();}now = st.back();}}for(char x : res){cout << x;}return 0;
}