记录编号	159765	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.215 s
提交时间	2015-04-22 17:16:26	内存使用	8.90 MiB

#include<fstream>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
#include<cstdio>
#define MAXN 1000001
using namespace std;
ifstream fin("censor.in");
ofstream fout("censor.out");
struct trie
{
	int flag;
	trie* s[26];
	trie* fail;
	trie()
	{
		memset(s,0,sizeof(s));
		fail=NULL;
		flag=0;
	}
};
trie* pos[MAXN];
string A;
char ch[MAXN];
int len[MAXN],M;
trie *root;
void MAKE_TRIE()
{
	root=new trie;
	string st;
	fin>>A;
	fin>>M;
	for(int i=1;i<=M;i++)
	{
		fin>>st;
		len[i]=st.length();
		trie *now=root;
		for(int j=0;j<len[i];j++)
		{
			if(now->s[st[j]-'a']==NULL) 
				now->s[st[j]-'a']=new trie;
			now=now->s[st[j]-'a'];
		}
		now->flag=i;
	}
}
trie* find(trie *x,int y)
{
	while(1)
	{
		if(x->s[y]!=NULL) return x->s[y];
		if(x==root) return root;
		x=x->fail;
	}
	return root;
}
void MAKE_FAIL()
{
	queue<trie*>q;
	q.push(root);
	root->fail=root;
	while(!q.empty())
	{
		trie *cur=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(cur->s[i]!=NULL)
			{
                if(cur==root) cur->s[i]->fail=root;
                else cur->s[i]->fail=find(cur->fail,i);
                q.push(cur->s[i]);
			}
			else cur->s[i]=find(cur,i);
		}
	}
}
void SCAN_PASG()
{
	int tot=0;
	trie* now=root;
	pos[0]=root;
	int l=A.length();
	for(int i=0;i<l;i++)
	{
		now=now->s[A[i]-'a'];
		tot++;
		pos[tot]=now;
		ch[tot]=A[i];
		if(now->flag!=0)
		{
			tot-=len[now->flag];
			now=pos[tot];
		}
	}
	for(int i=1;i<=tot;i++) fout<<ch[i];
	fout<<endl;
}
int main()
{
	MAKE_TRIE();
	MAKE_FAIL();
	SCAN_PASG();
	return 0;
}