记录编号	159203	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.328 s
提交时间	2015-04-20 12:15:18	内存使用	54.86 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int L_N=1e6+10;

int last[L_N],f[L_N],nxt[L_N/10][26],val[L_N],node_cnt;
int cache[L_N/10][26],vis[L_N/10][26];
int M;

char str[L_N],tmps[L_N];
int nt[L_N],lt[L_N],pos[L_N],N;

int get_nxt(int fa[],int i){
	if(fa[i]!=i) fa[i]=get_nxt(fa,fa[i]);
	return fa[i];
}
int idx(int c){
	return c-'a';
}

int main(){
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	scanf("%s",str+1);
	scanf("%d",&M);
	
	for(int i=1;i<=M;i++){
		scanf("%s",&tmps);
		int x=0,j=0;
		for(j=0;tmps[j];j++){
			int c=idx(tmps[j]);
			if(!nxt[x][c]) nxt[x][c]=++node_cnt;
			x=nxt[x][c];
		}
		val[x]=j;
	}
	
	queue<int> q;
	for(int i=0;i<26;i++) if(nxt[0][i]){
		int x=nxt[0][i];
		q.push(x);
		if(val[x]) f[x]=x;
	}
	while(q.size()){
		int u=q.front(); q.pop();
		for(int i=0;i<26;i++)if(nxt[u][i]){
			int v=nxt[u][i];
			
			int j=last[u];
			while(j && !nxt[j][i]) j=last[j];
			if(nxt[j][i]) j=nxt[j][i];
			
			last[v]=j;
			f[v]=val[v]?v:f[j];
			
			q.push(v);
		}
	}
	
	N=strlen(str+1);
	for(int i=1;i<=N+1;i++) nt[i]=lt[i]=i;
	
	int j=0;
	for(int i=1;i<=N;i=get_nxt(nt,i+1)){
		//if(i%10000==0)
		//	printf("%d\n",i);
			
		
		int c=idx(str[i]);
		int tj=j;
		if(!vis[tj][c]){
			while(j && !nxt[j][c]) j=last[j];
			if(nxt[j][c]) j=nxt[j][c];
			vis[tj][c]=true;
			cache[tj][c]=j;
		}else{
			j=cache[tj][c];
		}
		
		pos[i]=j;
		
		if(f[j]){
			j=f[j];
			int len=val[j];

			while(len--){
				nt[i]=i+1;
				lt[i]=i-1;
				i=get_nxt(lt,i);
			}
			
			j=pos[i];
		}
	}
	
	for(int i=get_nxt(nt,1); i<=N; i=get_nxt(nt,i+1)){
		printf("%c",str[i]);
	}
	printf("\n");
	
	return 0;
}