比赛 20160419s 评测结果 AAAAAAAAAA
题目名称 情书 最终得分 100
用户昵称 瑆の時間~無盡輪迴·林蔭 运行时间 1.011 s
代码语言 C++ 内存使用 231.43 MiB
提交时间 2020-05-09 10:52:48
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<cstring>
#define R register
using namespace std;
int fair[2000001],PD[2000001];
bool PDS[2000001];
int tire[2000001][26];
int tot=0,n;
string X;
inline void ADD(string x)
{
	R int p=0;
	for(R int i=0;i<x.size();i++)
	{
		if(tire[p][x[i]-'a'])
		{
			p=tire[p][x[i]-'a'];
		}
		else
		{
			tire[p][x[i]-'a']=++tot;
			p=tot;
		}
	}
	PD[p]++;
}
inline void Makefair()
{
	queue<int> q; 
	for(R int i=0;i<26;i++)
	{
		if(tire[0][i])
			q.push(tire[0][i]);
	}
	while(q.size())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(tire[p][i])
			{
				//fair[tire[p][i]]=tire[fair[p]][i];
				q.push(tire[p][i]);
				int FA=fair[p];
				while(FA&&!tire[FA][i])
					FA=fair[FA];
				fair[tire[p][i]]=tire[FA][i];
			}
			else
				tire[p][i]=tire[fair[p]][i];
		}
	}
}
inline int AC(char *x)
{
	R int p=0,ans=0,SE=strlen(x)-1;
	for(R int i=0;i<SE;i++)
	{
		p=tire[p][x[i]-'a'];
		for(int j=p;j&&PDS[j]!=-1;j=fair[j])
		{
			ans+=PD[j];
			PDS[j]=-1;
		}
	}
	return ans;
}
char WED[2350010];
int main()
{
	freopen("lettera.in", "r", stdin);
	freopen("lettera.out", "w", stdout);
	scanf("%d",&n);
	for(R int i=1;i<=n;i++)
	{
		cin>>X;
		ADD(X);
	}
	Makefair();
	while(scanf("%s",WED)!=EOF)
	{
		memset(PDS,0,sizeof(0));
		if(AC(WED)==n)
		{
			puts("Yes");
		} 
		else
			puts("No");
	}
	return 0;
}