记录编号	159240	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.183 s
提交时间	2015-04-20 14:29:10	内存使用	6.51 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define Nil NULL
const int SIZES=1000010,SIZEN=100010;
class Node{
public:
	int flag;//是否敏感词
	Node* ch[26];
	Node* fail;
	Node(){
		flag=-1;
		memset(ch,0,sizeof(ch));
		fail=Nil;
	}
};
Node *root;
Node* step(Node *x,int k){
	while(true){
		if(x->ch[k]!=Nil) return x->ch[k];
		if(x==root) return root;
		x=x->fail;
	}
}
queue<Node*> Q;
void make_automaton(void){
	root->fail=root;
	Q.push(root);
	while(!Q.empty()){
		Node *x=Q.front();Q.pop();
		for(int i=0;i<26;i++){
			if(x->ch[i]!=Nil){
				if(x==root) x->ch[i]->fail=root;
				else x->ch[i]->fail=step(x->fail,i);
				Q.push(x->ch[i]);
			}
			else x->ch[i]=step(x,i);
		}
	}
}
char S[SIZES];
int M;
int len[SIZEN]={0};
char str[SIZEN];
Node* pos[SIZES];
char ans[SIZES];
int tot=0;
void work(void){
	int L=strlen(S+1);
	Node *now=root;
	pos[0]=root;
	for(int i=1;i<=L;i++){
		now=now->ch[S[i]-'a'];
		tot++;
		pos[tot]=now;
		ans[tot]=S[i];
		if(now->flag!=-1){
			int k=now->flag;
			tot-=len[k];
			now=pos[tot];
		}
	}
	for(int i=1;i<=tot;i++) printf("%c",ans[i]);
	printf("\n");
}
void init(void){
	root=new Node;
	scanf("%s",S+1);
	scanf("%d",&M);
	for(int i=1;i<=M;i++){
		scanf("%s",str);
		len[i]=strlen(str);
		Node *now=root;
		for(int j=0;j<len[i];j++){
			int k=str[j]-'a';
			if(now->ch[k]==Nil) now->ch[k]=new Node;
			now=now->ch[k];
		}
		now->flag=i;
	}
}
int main(){
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	init();
	make_automaton();
	work();
	return 0;
}