记录编号	332736	评测结果	AAAAAAAAAA
题目名称	情书	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.354 s
提交时间	2016-10-29 09:06:04	内存使用	13.02 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
void insert(const char*,int);
void getfail();
void match(const char*);
void inc(int);
int n,ch[maxn][26]={{0}},fail[maxn]={0},last[maxn]={0},val[maxn]={0},q[maxn],head=0,tail=0,cnt=0,a[110];
char s[1350010],c;
bool ok;
int main(){
#define MINE
#ifdef MINE
	freopen("lettera.in","r",stdin);
	freopen("lettera.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%*[^a-z]");
		scanf("%[a-z]",s);
		insert(s,i);
	}
	getfail();
	for(;;){
		scanf("%*[^a-z]");
		if(scanf("%[a-z]",s)!=1)break;
		fill_n(a+1,n,0);
		match(s);
		ok=true;
		for(int i=1;i<=n;i++)if(!a[i]){
			ok=false;
			break;
		}
		printf(ok?"Yes\n":"No\n");
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void insert(const char *c,int i){
	int x=0;
	while(*c){
		if(!ch[x][*c-'a'])ch[x][*c-'a']=++cnt;
		x=ch[x][*c-'a'];
		c++;
	}
	val[x]=i;
}
void getfail(){
	int x,y;
	for(int c=0;c<26;c++)if(ch[0][c])q[tail++]=ch[0][c];
	while(head!=tail){
		x=q[head++];
		for(int c=0;c<26;c++){
			if(ch[x][c]){
				q[tail++]=ch[x][c];
				y=fail[x];
				while(y&&!ch[y][c])y=fail[y];
				fail[ch[x][c]]=ch[y][c];
				last[ch[x][c]]=val[fail[ch[x][c]]]?fail[ch[x][c]]:last[fail[ch[x][c]]];
			}
			else ch[x][c]=ch[fail[x]][c];
		}
	}
}
void match(const char *c){
	int x=0;
	while(*c&&*c!='$'){
		x=ch[x][*c-'a'];
		if(val[x])inc(x);
		else if(last[x])inc(last[x]);
		c++;
	}
}
void inc(int x){
	if(!x)return;
	a[val[x]]++;
	inc(last[x]);
}