模板 AC自动机

题目描述

有$N$ 个由小写字母组成的模式串以及一个文本串$T$ 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串$T$ 中出现的次数最多。

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数$N$ ，表示共有$N$ 个模式串，$1 leq N leq 150$ 。

接下去$N$ 行，每行一个长度小于等于$70$ 的模式串。下一行是一个长度小于等于$10^6$ 的文本串$T$ 。

输入结束标志为$N=0$ 。

输出格式：

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入输出样例

输入样例#1：

2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

输出样例#1：

4
aba
2
alpha
haha
传送门
AC自动机板子

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 char s[152][72],ss[1000001];
 9 int n,ch[15001][27],size,val[15001],f[15001],ans,cnt[15001],ansnum;
10 queue<int>Q;
11 void insert(int len,int id)
12 {int i;
13   int now=0;
14   for (i=0;i<len;i++)
15     {
16       if (ch[now][s[id][i]-'a']==0)
17     ch[now][s[id][i]-'a']=++size;
18       now=ch[now][s[id][i]-'a'];
19     }
20   val[now]=id;
21 }
22 void AC_build()
23 {int i;
24   for (i=0;i<26;i++)
25     if (ch[0][i])
26       f[ch[0][i]]=0,Q.push(ch[0][i]);
27   while (Q.empty()==0)
28     {
29       int u=Q.front();
30       Q.pop();
31       for (i=0;i<26;i++)
32     {
33       if (ch[u][i]) f[ch[u][i]]=ch[f[u]][i],Q.push(ch[u][i]);
34       else ch[u][i]=ch[f[u]][i]; 
35     }
36     }
37 }
38 void query()
39 {int i,j;
40   int now=0;
41   int len=strlen(ss);
42   for (i=0;i<len;i++)
43     {
44       now=ch[now][ss[i]-'a'];
45       for (j=now;j&&val[j]!=-1;j=f[j])
46     cnt[val[j]]++;
47     }
48 }
49 int main()
50 {int i;
51   while (cin>>n&&n)
52     {
53       size=0;
54       memset(ch,0,sizeof(ch));
55       memset(cnt,0,sizeof(cnt));
56       memset(val,0,sizeof(val));
57       for (i=1;i<=n;i++)
58     {
59       scanf("%s",s[i]);
60       insert(strlen(s[i]),i);
61     }
62       AC_build();
63       scanf("%s",ss);
64       query();
65       ans=0;
66       for (i=1;i<=n;i++)
67     if (cnt[i]>ans)
68       {
69         ans=cnt[i];
70       }
71       printf("%d
",ans);
72       for (i=1;i<=n;i++)
73     if (cnt[i]==ans)
74       {
75         printf("%s
",s[i]);
76       }
77     }
78 }