比赛 20160419s 评测结果 ATTAAAATTT
题目名称 情书 最终得分 50
用户昵称 mikumikumi 运行时间 5.008 s
代码语言 C++ 内存使用 1.97 MiB
提交时间 2016-04-19 11:24:49
显示代码纯文本
#include<cstdio>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEM=1350010,SIZEN=110;
char str[SIZEM];
bool vis[SIZEN];
queue<int> Q;
int pos;
int N;
class miku
{
public:
	int cnt;
	int fail[SIZEN*SIZEN];
	int flag[SIZEN*SIZEN];
	map<char,int> next[SIZEN*SIZEN];
	miku()
	{
		cnt=1;
		memset(flag,0,sizeof(flag));
		for(int i=0;i<=200;i++) next[0][i]=1;
	}
	void built(char a[],int n,int id)
	{
		int now=1;
		for(int i=0;i<n;i++)
		{
			char c=a[i];
			if(!next[now][c]) next[now][c]=++cnt;
			now=next[now][c];
		}
		flag[now]=id;
	}
	void makefail()
	{
		fail[1]=0;
		Q.push(1);
		while(!Q.empty())
		{
			int x=Q.front();Q.pop();
			for(int i=0;i<=200;i++)
			{
				if(next[x][i])
				{
					int v=next[x][i];
					int k=fail[x];
					while(!next[k][i]) k=fail[k];
					fail[v]=next[k][i];
					Q.push(v);
				}
			}
		}
	}
	void dfs(int x)
	{
		if(!x) return;
		if(vis[x]) return;
		vis[x]=1;
		if(flag[x]) pos++;
		dfs(fail[x]);
	}
	void check(char a[])
	{
		int len=strlen(a)-1,now=1;
		pos=0;memset(vis,0,sizeof(vis));
		for(int i=0;i<len;i++)
		{
			int c=a[i];
			while(!next[now][c]) now=fail[now];
			now=next[now][c];
			dfs(now);
		}
		if(pos==N) printf("Yes\n");
		else printf("No\n");
	}
}AC;
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%s",str);
		//cout<<str<<endl;
		int len=strlen(str);
		AC.built(str,len,i);
	}
	AC.makefail();
}
void work()
{
	while(true) 
	{
		if(scanf("%s",str)==EOF) break;
		AC.check(str);
	}
}
int main()
{
	freopen("lettera.in","r",stdin);
	freopen("lettera.out","w",stdout);
	read();
	work();
	return 0;
}