记录编号	412865	评测结果	AAAAAAAAAA
题目名称	情书	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	1.315 s
提交时间	2017-06-10 10:48:10	内存使用	5.74 MiB

#include <bits/stdc++.h>
#define L 1350000
#define MAXN 100000
using namespace std;
bool via[101];
char w[L+100];
int n;


struct Trie{
    Trie *ch[26],*fail;
    vector<int>q;
    Trie():fail(NULL){
        q.clear();
        for(int x=0;x!=26;x++)ch[x]=NULL;
    }
    void* operator new (size_t size);
}*root = new Trie(),*C,*W;

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==W){
        C=new Trie[1<<15];
        W=C+(1<<15);
    }
    return C++;
}

Trie* q[100000];

void insert(char *s,int id){
    Trie * now = root;
    int len=strlen(s);
    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(id);
}

void build_AC(){
    root->fail=NULL;
    int l=0,r=1;
    q[l]=root;
    while(l<r){
        Trie *now = q[l++];
        for(int i=0;i<26;i++)
            if(now->ch[i]){
                Trie *rt = now-> fail;
                while(rt && rt->ch[i]==NULL)rt=rt->fail;
                now->ch[i]->fail=rt? rt->ch[i] : root;
                q[r++]=now->ch[i];
            }
    }
}

inline void work(){
    int ans=0;
    memset(via,0,sizeof(via));
    Trie *now =root;
    for(int i=0;w[i]!='$';i++){
        int to=w[i]-'a';
        while(now && now -> ch[to] == NULL)now = now-> fail;
        now = now ? now -> ch[to]:root;
        for(Trie* nown= now ;nown; nown = nown -> fail)
            if(!now->q.empty()){
                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);

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char s[1000];
        scanf("%s",s);
        insert(s,i);
    }
    build_AC();
    while(read())work();
    return 0;

}