把上题的KMP改成AC自动机。
注意root必须是0。因为root其实是NULL的意思。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 500050 using namespace std; char t[maxn],s[maxn]; int cases,l,son[maxn][30],fail[maxn],fath[maxn],root,tot=0,pre[maxn],ts[maxn],len[maxn]; queue <int> q; bool flag[maxn]; void insert() { int now=root; for (int i=0;i<l;i++) { int nb=s[i]-'a'+1; if (!son[now][nb]) son[now][nb]=++tot; now=son[now][nb]; if (i==l-1) len[now]=l; } } void build_AC() { q.push(root); while (!q.empty()) { int head=q.front();q.pop(); for (int i=1;i<=26;i++) { if (son[head][i]) { if (head!=root)fail[son[head][i]]=son[fail[head]][i]; else fail[son[head][i]]=root; q.push(son[head][i]); } else son[head][i]=son[fail[head]][i]; } } } void match_AC() { int now=root;ts[0]=1; for (int i=1;i<=l;i++) { int nb=t[i-1]-'a'+1; while (now!=root && !son[now][nb]) now=fail[now]; if (son[now][nb]) now=son[now][nb]; ts[i]=now; if (len[now]) { int p=i; for (int j=1;j<=len[now];j++) { flag[p-1]=true; p=pre[p]; } pre[i+1]=p;now=ts[p]; } } } int main() { scanf("%s",t); scanf("%d",&cases);root=tot=0; for (int i=1;i<=cases;i++) { scanf("%s",s); l=strlen(s);insert(); } build_AC(); l=strlen(t);for (int i=1;i<=l;i++) pre[i]=i-1; match_AC(); for (int i=0;i<l;i++) if (!flag[i]) printf("%c",t[i]); printf(" "); return 0; }