记录编号	411505	评测结果	AAAAAAAAAA
题目名称	情书	最终得分	100
用户昵称	Hzoi_Hugh	是否通过	通过
代码语言	C++	运行时间	1.395 s
提交时间	2017-06-05 12:28:39	内存使用	1.98 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define L 1350000
#define MAXN 100000
using namespace std;
char w[L+100];
bool via[101];
int n,ans;
struct Trie
{
	vector<int>q;
	Trie *ch[26],*fail;
	Trie(){q.clear();memset(ch,0,sizeof(ch));fail=NULL;}
	void* operator new(size_t size);
}*root,*C,*mempool,*q[MAXN];
inline int read()
{
	memset(w,0,sizeof(w));
	int l=0;
	char ch;
	if(cin>>ch){ while(ch!='$'){w[l++]=ch;ch=getchar();} w[l]=ch;return l;}
	else return 0;
}
void* Trie :: operator new(size_t size)
{
	if(C==mempool)
	{
	  C=new Trie[(1<<15)+10];
	  mempool=C+(1<<15)+10;
	}
	return C++;
}
inline void insert(char *s,int x)
{
	int len=strlen(s);
	Trie *now=root;
	for(int i=0;i<len;i++)
	{
	  if(now->ch[s[i]-'a']==NULL)
	   now->ch[s[i]-'a']=new Trie();
	  now=now->ch[s[i]-'a'];
	}
	now->q.push_back(x);
}
inline void build()
{
	root->fail=NULL;
	q[0]=root;
	for(int i=0,j=0;i<=j;i++)
	 for(int l=0;l<26;l++)
	 if(q[i]->ch[l])
	 {
	   Trie *now=q[i]->fail;
	   while(now&&!now->ch[l])now=now->fail;
	   q[i]->ch[l]->fail=now?now->ch[l]:root;
	   q[++j]=q[i]->ch[l];
	 }
}
inline void work()
{
	memset(via,0,sizeof(via));
	Trie *now=root;
	for(int i=0;w[i]!='$';i++)
	{
	   int to=w[i]-'a';
	   //cout<<"("<<now<<")";
	   while(now&&!now->ch[to])now=now->fail;
	   now=now?now->ch[to]:root;
	   //cout<<"("<<now<<")";
	   for(Trie *nown=now;nown;nown=nown->fail)
	   if(!nown->q.empty())
	   {
	   	  //cout<<"("<<nown<<")";
	   	  int l=nown->q.size();
	   	  for(int j=0;j<l;j++)
	   	   via[nown->q[j]]=1;
	   }
	}
	ans=0;
	for(int i=1;i<=n;i++)
	 if(via[i])ans++;
	if(ans==n)
	 printf("Yes\n");
	else
	 printf("No\n");
}
int main()
{
    freopen("lettera.in","r",stdin);
	freopen("lettera.out","w",stdout);
	root=new Trie();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	   char s[1000];
	   scanf("%s",s);
	   insert(s,i);
	}
	build();
	while(read()) work();
	return 0;
}