【题目大意】
有一个匹配串和多个模式串，现在不断删去匹配串中的模式串，求出最后匹配串剩下的部分。
【思路】
众所周知，KMP的题往往对应着一道AC自动机quq。本题同BZOJ3942（KMP）,这里改成AC自动机即可。
我一开始写了原始的AC自动机，写挂了。后来思考了一下，应当用Trie图，机智地1A。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=+;
char str[MAXN];
int n,cnt;
struct ACauto
{
ACauto* next[];
ACauto* fail;
int id;
int sign;
ACauto()
{
for (int i=;i<;i++) next[i]=NULL;
fail=NULL;
id=++cnt;
sign=;
}
}; ACauto* rt=new ACauto(); void insert(char* s,ACauto* rt)
{
ACauto* tmp=rt;
for (int i=;s[i];i++)
{
int index=s[i]-'a';
if (tmp->next[index]==NULL)
tmp->next[index]=new ACauto();
tmp=tmp->next[index];
}
tmp->sign=strlen(s);
} void buildfail(ACauto* rt)//这里我们建立Trie图而不是Trie树的AC自动机
{
queue<ACauto*> que;
que.push(rt);
while (!que.empty())
{
ACauto* head=que.front();que.pop();
for (int i=;i<;i++)
{
if (head->next[i]==NULL)
{
if (head==rt) head->next[i]=rt;
else head->next[i]=head->fail->next[i];
}
else
{
if (head==rt) head->next[i]->fail=rt;
else
{
head->next[i]->fail=head->fail->next[i];
//if (head->next[i]->fail->sign) head->next[i]->sign=head->next[i]->fail->sign;/*注意！*/
}
que.push(head->next[i]);
}
}
}
} void init()
{
cnt=;
scanf("%s",str);
scanf("%d",&n);
for (int i=;i<n;i++)
{
char s[MAXN];
scanf("%s",s);
insert(s,rt);
}
buildfail(rt);
} void solve()
{
ACauto* a[MAXN];
char stack[MAXN];
int top=;
a[top]=rt;
for (int i=;str[i];i++)
{
ACauto* j=a[top];
stack[++top]=str[i];
int index=str[i]-'a';
a[top]=j->next[index];
if (a[top]->sign) top-=a[top]->sign;
}
stack[top+]='\0';
puts(stack+);
} int main()
{
init();
solve();
return ;
}