Description
Oimaster and sevenk love each other.
But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman’s nature, s
evenk felt angry and began to check oimaster’s online talk with ChuYuXun. Oimaster talked with Ch
uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, “how
many strings in oimaster’s online talk contain this string as their substrings?”
有n个大串和m个询问，每次给出一个字符串s询问在多少个大串中出现过
Input
There are two integers in the first line,
the number of strings n and the number of questions q.
And n lines follow, each of them is a string describing oimaster’s online talk.
And q lines follow, each of them is a question.
n<=10000, q<=60000
the total length of n strings<=100000,
the total length of q question strings<=360000
Output
For each question, output the answer in one line.
Sample Input
3 3
abcabcabc
aaa
aafe
abc
a
ca
abcabcabc
aaa
aafe
abc
a
ca
Sample Output
1
3
1
3
1
HINT
Source
鸣谢duan2提供译文
Solution
广义后缀自动机。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=200100; int n,Q,cnt,last,now,maxlen[N],a[N][26],fa[N],vis[N],num[N]; char s[360010]; void extend(int c) { int p=last,np;np=last=++cnt; maxlen[np]=maxlen[p]+1; while (!a[p][c]&&p) a[p][c]=np,p=fa[p]; if (!p) fa[np]=1; else { int q=a[p][c]; if (maxlen[q]==maxlen[p]+1) fa[np]=q; else { int nq=++cnt; maxlen[nq]=maxlen[p]+1; vis[nq]=vis[q]; num[nq]=num[q]; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (a[p][c]==q) a[p][c]=nq,p=fa[p]; } } while (np) { if (vis[np]!=now) vis[np]=now,num[np]++; else break; np=fa[np]; } } int main() { scanf("%d%d",&n,&Q); cnt=1; for (int i=1;i<=n;i++) { scanf("%s",s+1); int len=strlen(s+1); last=1; now=i; for (int j=1;j<=len;j++) extend(s[j]-'a'); } while (Q--) { scanf("%s",s+1); int len=strlen(s+1),id=1; for (int i=1;i<=len;i++) { id=a[id][s[i]-'a']; if (!id) break; } printf("%d\n",num[id]); } return 0; } |
