记录编号	160969	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.226 s
提交时间	2015-04-30 10:44:17	内存使用	6.99 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
 
#define N 1000010
#define M 26
 
using namespace std;
 
void file(){
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
}
 
struct node{
	node *ch[M],*fail;
	int v,len;
}*root,*next[N];
 
void addin(char *c){
	node* tmp=root;
	int len=strlen(c);
	while(*c!='\0'){
		int t=*c-'a';
		if(tmp->ch[t]==NULL) tmp->ch[t]=new node();
		tmp=tmp->ch[t];
		c++;
	}
	tmp->v=max(len,tmp->v);
}
 
queue<node*> q;
 
void getfail(){
	q.push(root);
	while(!q.empty()){
		node* tmp=q.front(); q.pop();
		for(int t=0;t<M;t++){
			if(tmp->ch[t]!=NULL){
				if(tmp==root) tmp->ch[t]->fail=root;
				else tmp->ch[t]->fail=tmp->fail->ch[t];
				q.push(tmp->ch[t]);
			}
			else{
				if(tmp==root) tmp->ch[t]=root;
				else tmp->ch[t]=tmp->fail->ch[t];
			}
			node* p=tmp->ch[t];
			if(tmp->ch[t]==root) p->len=p->v;
			else p->len=max(p->v,p->fail->len);
		}
	}
}
 
char ans[N],S[N];
int tot;
 
void ask(char *c){
	node* tmp=root;
	tot=0;
	next[0]=root;
	while(*c!='\0'){
		int t=*c-'a',len=0;
		ans[++tot]=*c;
		tmp=tmp->ch[t];
		next[tot]=tmp;
		tot-=tmp->len;
		tmp=next[tot];
		c++;
	}
	for(int i=1;i<=tot;i++) putchar(ans[i]);
	putchar('\n');
}
 
int n;
char str[N];
 
int main(){
	file();
	root=new node();
	scanf("%s",S);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		addin(str);
	}
	getfail();
	ask(S);
	fclose(stdin);
	fclose(stdout);
	return 0;
}