P3796 【模板】AC自动机(加强版)

题目描述

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

输入输出格式

输入格式:

输入含多组数据。

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

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

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

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
12
13
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

输出样例#1:

1
2
3
4
5
4
aba
2
alpha
haha

题解

标记打在模式串上。

还是模板

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y)
{
if (x<y) x=y;
}
int qmin(int &x,int y)
{
if (x>y) x=y;
}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(isdigit(s))
{
k=k*10+(s^'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=1e6+100;
struct node
{
int ch[26],end,fail;
} a[maxn];
int n,id;
queue<int> q;
char CH[maxn];
inline void clean(int x)
{
for (int i=0;i<=25;i++) a[x].ch[i]=0;
a[x].end=0;a[x].fail=0;
}
inline void build(int x)
{
int len=strlen(CH+1);
int now=0;
for (int i=1;i<=len;i++)
{
if (a[now].ch[CH[i]-'a']==0)
{
a[now].ch[CH[i]-'a']=++id;
clean(id);
}
now=a[now].ch[CH[i]-'a'];
}
a[now].end=x;
}
void get_fail()
{
for (int i=0;i<26;i++)
{
if (a[0].ch[i]!=0)
{
a[a[0].ch[i]].fail=0;
q.push(a[0].ch[i]);
}
}
while (!q.empty())
{
int u=q.front(),v;q.pop();
for (int i=0;i<26;i++)
{
v=a[u].ch[i];
if (v!=0)
{
a[v].fail=a[a[u].fail].ch[i];
q.push(v);
} else a[u].ch[i]=a[a[u].fail].ch[i];
}
}
}
struct node1
{
int id,num;
char c[80];
} ans[160];
void ac_query()
{
int len=strlen(CH+1);
int now=0,sum=0;
for (int i=1;i<=len;i++)
{
now=a[now].ch[CH[i]-'a'];
for (int t=now;t&&a[t].end!=-1;t=a[t].fail)
{
ans[a[t].end].num++;
}
}
}
int main()
{
while (true)
{
id=0;
n=read();
if (n==0) return 0;
clean(0);
for (int i=1;i<=n;i++)
{
ans[i].num=0;
ans[i].id=i;
}
for (int i=1;i<=n;i++)
{
scanf("%s",CH+1);
memcpy(ans[i].c,CH,sizeof(ans[i].c));
build(i);
}
a[0].fail=0;
get_fail();
scanf("%s",CH+1);
ac_query();
int sum=0;
for (int i=1;i<=n;i++)
{
qmax(sum,ans[i].num);
}
printf("%d\n",sum);
for (int i=1;i<=n;i++)
{
if (ans[i].num==sum)
{
printf("%s\n",ans[i].c+1);
}
}
}
return 0;
}