比赛 20160419s 评测结果 ATAAAAATTT
题目名称 情书 最终得分 60
用户昵称 Satoshi 运行时间 4.955 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-04-19 11:19:46
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <queue>
#include <string>
#define N 210
using namespace std;
ifstream in("lettera.in");
ofstream out("lettera.out");
int n;
string TT[110];
string SS;
int nex[N]={0};
void getnext(string S)
{
	int i=0,j=-1;
	nex[0]=-1;
	while(i<S.length())
	{
		while(j!=-1&&S[i]!=S[j])j=nex[j];
		nex[++i]=++j;
	}
}
int KMP(string S,string T)
{
	int i,j;
	int ans=0;
	i=j=0;
	getnext(T);
	while(i<S.length())
	{
		while(j!=-1&&S[i]!=T[j])j=nex[j];
		i++;j++;
		if(j==T.length())ans++;
	}
	return ans;
}
int main()
{
	int i,tim;
	bool flag=1;
	in>>n;
	for(i=1;i<=n;i++)in>>TT[i];
	while(in>>SS)
	{
		flag=1;
		tim=0;
		SS.erase(SS.length()-1);
		for(i=1;i<=n;i++)
		{
			tim=KMP(SS,TT[i]);
			//out<<tim<<' ';
			if(!tim)
			{
				flag=0;
				break;
			}
		}
		//out<<endl;
		if(flag)out<<"Yes"<<endl;
		else out<<"No"<<endl;
	}
	return 0;
}