记录编号	159371	评测结果	AWWWTTWTTTTTWWA
题目名称	审查	最终得分	13
用户昵称	ggwdwsbs	是否通过	未通过
代码语言	C++	运行时间	7.047 s
提交时间	2015-04-20 23:32:52	内存使用	103.67 MiB

#include<stdio.h>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1e6+10;
struct tire
{
	int ch[26];
	int fail;
	int val;
}tree[maxn];
//vector<tire>tree;
char s1[maxn/10];
char s[maxn];
int vis[maxn];
int leng[maxn];
int pos[maxn];
int n,root=0;
int now,m=0;
int id(char c)
{
	return c-'a';
}
int Erase(int l,int r)
{
	//for(int i=l;i<=r;i++) vis[i]=1;
	while(r>=l)
	{
		while(vis[r])
		{
			l--;
			r--;
		}
		vis[r]=1;
		r--;
	}
}
int build_tire(char *s1,int v)
{
	int l=strlen(s1);
	now=root;
	for(int i=0;i<l;i++) 
	 if(!tree[now].ch[id(s1[i])]) 
	 {
	 	m++;
	 	tree[now].ch[id(s1[i])]=m;
	 	now=m;
		memset(tree[now].ch,0,sizeof(tree[now].ch));
	 	tree[now].fail=tree[now].val=0;
	 }
	 else now=tree[now].ch[id(s1[i])];
	tree[now].val=v; 
}
int build()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s1);
		leng[i]=strlen(s1);
		build_tire(s1,i);
	}
	queue<int>q;
	tree[root].fail=root;
	for(int i=0;i<26;i++)
	 if(tree[root].ch[i])
	 {
	 	 tree[tree[root].ch[i]].fail=root;
	 	 q.push(tree[root].ch[i]);
	 }
	while(q.size()>0)
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(!tree[u].ch[i]) tree[u].ch[i]=tree[tree[u].fail].ch[i];
			else
			{
				int v=tree[u].fail;
				while(v&&!tree[v].ch[i]) v=tree[v].fail;
				tree[u].fail=tree[v].ch[i];
		 		q.push(tree[u].ch[i]);
			}
		}
	}
}
int find()
{
	int l=strlen(s);
	int j=0;
	for(int i=0;i<l;i++)
	 {
		//while(j&&!tree[j].ch[id(s[i])]) j=tree[j].fail;
		j=tree[j].ch[id(s[i])];
		if(tree[j].val!=0)
		{
			Erase(i-leng[tree[j].val]+1,i);
			j=pos[i-leng[tree[j].val]];
		}
 	 }
}
int main()
{
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	scanf("%s",s);
	build();
	int l=strlen(s);
	int j=0; 
	for(int i=0;i<l;i++)
	{
		j=tree[j].ch[id(s[i])];
		pos[i]=j;
	}
	find();
	for(int i=0;i<l;i++)
	 if(!vis[i]) printf("%c",s[i]);
}
/*
begintheescapexecutionatthebreakofdawn
2
escape
execution*/