比赛 20150420 评测结果 TTTTTTTTTTTTTTT
题目名称 审查 最终得分 0
用户昵称 STARGAZER 运行时间 15.000 s
代码语言 C++ 内存使用 7.77 MiB
提交时间 2015-04-20 11:53:27
显示代码纯文本
/*
1942. 审查
★   输入文件:censor.in   输出文件:censor.out   简单对比
时间限制:1 s   内存限制:256 MB
【题目描述】
农夫约翰为他的奶牛们购买了一份名字叫Good Hooveskeeping的定期杂志,
因此奶牛们在挤奶期间就有了大量的阅读素材。遗憾的是在最新的一期上,
有一篇有点儿不适当的文章,是关于如何烹饪完美的牛排。
FJ不想让她们看到那篇文章,(显然,这份杂志需要更好的编辑监督)。
FJ已经采集了杂志的所有文本,并将其创建成了一个长度最多10^6个字符的字符串。
他有一个审查出来的想要从这个字符串中删除的发生不适当内容的一组子串t_1 ...t_N。
这样,农民约翰会找到串S中最早出现的一个被审查出来的词(在最开始给的单词序列里)
并从串S中删除它,他接着再重复这个过程,继续在串S中删除当前最早出现的审查出来的单词。
重复这个过程,直到S中没有被审查出来单词出现。
注意:每次删除操作发生后可能创建出一个在以前串S中是不存在的新的(单词列表中有的)单词。
农民约翰注意到,审查出来的一个待删词不会作为另一个待删词的子串出现。特别的这意味着串S中最早出现的待删词是唯一的。
请帮助FJ确定最终的审查内容
【输入格式】
第一行包含S.
第二行包含N,即审查出来的单词的数量。
接下来的N行包含字符串t_1…t_n。每个字符串将只包含小写字母(范围在a...z)
,并且所有这些字符串的组合长度将最多是10^5。
【输出格式】
删除操作完成后形成的新的字符串S(这里保证删除过程中不会出现空串)。
【样例输入】
begintheescapexecutionatthebreakofdawn
2
escape
execution
【样例输出】
beginthatthebreakofdawn 
*/
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
struct S
{
	char a;
	S *next;
}s[1000000],*pos,*p;
int n,i,b=0,e,j;
string t[100000];
int match(int x,S *poi)
{
	if(x!=t[j].size()-1)
	{
		if(t[j][x]==poi->a)
			return 1&match(x+1,poi->next);
		return 0;
	}
	else
	{
		if(t[j][x]==poi->a)
		{
			p=poi;
			return 1;
		}
		return 0;
	}
}
int scan()
{
	pos=&s[b];
	while(pos!=s[e].next)
	{
		j=0;
		while(j<n)
		{
			if(pos->a==t[j][0])
			{
				if(match(0,pos)==1)
				{
					pos->next=p->next;
				    goto Other;
				}
			}
			j++;
		}
		pos=pos->next;
	}
	return 0;
	Other:
	scan();
	return 0;
}
int main(){
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	cin>>t[0];
	i=0;
	while(i!=t[0].size())
	{
		s[i].a=t[0][i];
		if(i!=t[0].size()-1)
			s[i].next=&s[i+1];
	}
	cin>>n;
	e=n-1;
	s[e].next=NULL;
	for(i=0;i<n;i++)
		cin>>t[i];
	scan();
	pos=&s[b];
	do
	{
		cout<<pos->a;
		pos=pos->next;
	}while(pos!=s[e].next);
	cout<<endl;
	return 0;
}