Meteor

每隔33年，狮子星宫的仙女们都要下凡游历一趟，她们包裹着纯白的冰鲛縠，在轩辕之光的庇护下降临人间。所以

在凡间的人们并不能看清仙女们的真面目，只能见到若干束星光--我们称之为流星。仙女们的下凡游历需要经过狮

子座守护神Saint Leo的允许。Saint Leo会从掌管天界出口的神那里得到一个羊皮卷，如果某个仙女的称谓包含在

羊皮卷上，她就被允许前往人间（不同的仙女的称谓可以在文本里重叠，即他们是独立存在的）。羊皮卷上记录了

一个很长的小写拉丁字符文本，每个仙女的称谓也是一个小写拉丁字符串。例如文本是：saintzeuscynthiathenahere那么仙女cynthia、athena就都被入选了（下划线部分包含了这两个名字），而hera就不能被选上（因为不包含

在文本里面）。作为Saint Leo的助手，你的任务是帮Leo完成选人的这个繁琐的工作。

Input

第一行为一个整数n，表示文本的长度；

第二行为一个长度为n的字符串文本；

第三行为一个整数m，表示待选的仙女的个数；

下接m行，第i行一个字符串，表示第i个仙女的称谓。

n<=10^5，m<=10^5

Output

包含m行，若第i个仙女被选上，则第i行输出YES，否则输出NO。

Sample Input

saintzeuscynthiathenahere

cynthia

hera

athena

sol：AC自动机模板，注意下重复单词的处理。

 1 #pragma GCC optimize(2)
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int MAXN=1000000;
 5 struct Trie{
 6     int son[26];
 7     int cnt;
 8     int fail;
 9 }AC[MAXN];
10 int n,m,tot=0,iidd[MAXN];
11 bool ans[MAXN];
12 char S[MAXN],T[MAXN];
13 void add(char *s,int len,int id)
14 {
15     int now=0;
16     for(register int i=0;i<len;i++)
17     {
18         if(!AC[now].son[s[i]-'a'])
19           AC[now].son[s[i]-'a']=++tot;
20         now=AC[now].son[s[i]-'a'];
21     }
22     if(AC[now].cnt)//如果当前单词之前出现过
23       iidd[id]=AC[now].cnt; //该单词的id修改为之前出现过的单词id 
24     else
25       AC[now].cnt=id;//记录下当前now节点是第id各单词的结尾 
26 }
27 void get_fail()
28 {
29     queue<int> q;
30     AC[0].fail=0;
31     for(register int i=0;i<26;i++)
32     {
33         if(AC[0].son[i])
34         {
35             AC[AC[0].son[i]].fail=0;
36             q.push(AC[0].son[i]);  
37         }
38     }
39     while(!q.empty())
40     {
41         int u=q.front();
42         q.pop();
43         for(register int i=0;i<26;i++)
44         {
45             if(AC[u].son[i])//u下面的i节点存在 
46                {
47                 AC[AC[u].son[i]].fail=AC[AC[u].fail].son[i];
48                 q.push(AC[u].son[i]);  
49                }
50             else
51                   AC[u].son[i]=AC[AC[u].fail].son[i];
52         }
53     }
54 }
55 void AC_query(char *s,int len)
56 {
57     int now=0;
58     for(register int i=0;i<len;i++)
59     {
60         now=AC[now].son[s[i]-'a'];
61         for(register int t=now;t;t=AC[t].fail)
62          {
63             if(AC[t].cnt&&ans[AC[t].cnt]) break;
64             ans[AC[t].cnt]=true;
65         }
66     }
67 }
68 int main(){
69     scanf("%d",&n);
70     scanf("%s",S);
71     scanf("%d",&m);
72     for(register int i=1;i<=m;i++) iidd[i]=i;
73     for(register int i=1;i<=m;i++)
74     {
75         scanf("%s",T);
76         add(T,strlen(T),i);
77     }
78     get_fail();
79     AC_query(S,n);
80     for(register int i=1;i<=m;i++){
81         if(ans[iidd[i]]) printf("YES
");
82         else printf("NO
");
83     }
84     return 0;
85 }