记录编号	159337	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.641 s
提交时间	2015-04-20 20:39:59	内存使用	2.29 MiB

#include<cstdio>
#include<deque>
#include<string>
#include<iostream>
using namespace std;
string a,b[100001];
char ans[1000001];
int n,len[100000]={0};
class miku
{
public:
	int link[27];
	int fail;
	int flag;
	miku()
	{
		for(int i=0;i<26;i++)
			link[i]=-1;
		fail=-1;
		flag=-1;
	}
};
deque<miku> q;
int tire(string c,int i)
{
	int root=0,le=c.length();
	for(int j=0;j<le;j++)
	{
		int t=c[j]-'a';
		if(q[root].link[t]==-1)
		{
			miku x;
			q[root].link[t]=q.size();
			q.push_back(x);
		}
		root=q[root].link[t];
	}
	q[root].flag=i;
	return 0;
}
int step(int x,int y)
{
	while(true)
	{
		if(q[x].link[y]!=-1) return q[x].link[y];
		else if(x==0) return 0;
		x=q[x].fail;
	}
}
int makefail()
{
	int root=0;
	deque<int> Q;
	q[0].fail=0;
	Q.push_back(0);
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop_front();
		for(int i=0;i<26;i++)
		{
			if(q[x].link[i]!=-1)
			{
				if(x==0) q[q[x].link[i]].fail=0;
				else
					q[q[x].link[i]].fail=step(q[x].fail,i);
				Q.push_back(q[x].link[i]);
			}
			else q[x].link[i]=step(x,i);
		}
	}
	return 0;
}
int main()
{
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	cin>>a;
	miku x;
	q.push_back(x);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		len[i]=b[i].length();
		tire(b[i],i);
	}
	makefail();
	int le=a.length(),root=0,pos[100000]={0},tot=0;
	for(int i=0;i<le;i++)
	{
		int t=a[i]-'a';
		if(q[root].link[t]!=-1)
			root=q[root].link[t];
		else
		   root=step(q[root].fail,t);
		tot++;
		pos[tot]=root;
		ans[tot]=a[i];
		if(q[root].flag!=-1)
		{
			tot-=len[q[root].flag];
			root=pos[tot];
		}
	}
	for(int i=1;i<=tot;i++)
		cout<<ans[i];
	/*for(int i=0;i<q.size();i++)
	{
		cout<<i<<" "<<q[i].flag<<" "<<q[i].fail<<endl;
		for(int j=0;j<26;j++)
		cout<<q[i].link[j]<<" ";
		cout<<endl;
	}*/
	return 0;
}