比赛 20150420 评测结果 AWWWWAWWWWWWWWA
题目名称 审查 最终得分 20
用户昵称 Satoshi 运行时间 0.740 s
代码语言 C++ 内存使用 0.69 MiB
提交时间 2015-04-20 10:32:08
显示代码纯文本
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream in("censor.in");
ofstream out("censor.out");
/*class node
{
public:
	int l;
	int r;
}art[100001],bob[100001];
class nobe
{
public:
	bool h;
	int royal;
}pob[1000001];*/
string p,s;
int n;
int next[100001]={0};
int saber=0;
/*bool com(node a,node b)
{
	if(a.l<b.l)return 1;
	if(a.l==b.l)
	{
		if(a.r<b.r)return 1;
	}
	return 0;
}
void mark(int count)//区间合并
{
	int i,debug;
	for(i=1;i<=count-1;i++)
	{
		if(art[i].r>=art[i+1].r)
		{
			art[i+1]=art[i];
			continue;
		}
		if(art[i].r<art[i+1].l)continue;
		art[i].r=art[i+1].r;
		art[i+1].l=art[i].l;
	}
	for(i=1;i<=count-1;i++)
	{
		if(art[i].l==art[i+1].l)
		{
			debug=max(art[i].r,art[i+1].r);
			art[i].r=art[i+1].r=debug;
		}
		if(art[i].r==art[i+1].r)
		{
			debug=min(art[i].l,art[i+1].l);
			art[i].l=art[i+1].l=debug;
		}
	}
	for(i=1;i<=count-1;i++)
	{
		if(art[i].r==art[i+1].r&&art[i].l==art[i+1].l)
		{
			art[i].l=-1;
			art[i].r=-1;
		}
	}
	for(i=1;i<=count;i++)
	{
		if(art[i].l!=-1)
		{
			saber++;
			bob[saber].l=art[i].l-1;
			bob[saber].r=art[i].r-1;
		}
	}
	//for(i=1;i<=saber;i++)out<<bob[i].l<<' '<<bob[i].r<<endl;
}*/
int kmp()
{
	int i,j;
	int M=p.length();
	int N=s.length();
	i=j=0;
	while(i<N&&j<M)
	{
		if(j<0||s[i]==p[j])
		{
			i++;
			j++;
		}
		else j=next[j];
	}
	//out<<i<<' '<<M<<' '<<1<<endl;
	if(j>=M)return i-M+1;
	else return -1;
}
void makenext(string p)
{
	int i,j;
	i=0;
	j=-1;
	next[0]=-1;
	while(i<p.length()-1)
	{
		if(j<0||p[i]==p[j])
		{
			i++;
			j++;
			next[i]=j;
		}
		else j=next[j];
	}
}
int main()
{
	int i,j,o,l,r;int count=0;
	in>>s;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>p;
		//out<<p<<endl;
		makenext(p);
		o=kmp();
		if(o==-1)continue;
		else
	    {
			//count++;
			l=o-1;
			r=p.length();
			//out<<l<<' '<<r<<endl;
			s.erase(l,r);
		}
	}
	for(i=0;i<s.length();i++)
	{
		out<<s[i];
	}
	out<<endl;
	//in>>count;
	//for(i=1;i<=count;i++)in>>art[i].l>>art[i].r;
	//sort(art+1,art+count+1,com);
	//for(i=1;i<=count;i++)out<<art[i].l<<' '<<art[i].r<<endl;
	//mark(count);
	/*for(i=1;i<=saber;i++)out<<bob[i].l<<' '<<bob[i].r<<endl;
	for(i=1;i<=saber;i++)
	{
		pob[bob[i].l].h=1;
		pob[bob[i].l].royal=bob[i].r+1;
	}
	for(i=0;i<s.length();i++)
	{
		if(pob[i].h)i=pob[i].royal;
		out<<s[i];
	}*/
	//out<<endl;
	return 0;
}