[板子/笔记] AC自动机

Aho-Corasick Automaton能大力搞多串匹配。

简称AC自动机自动AC机


KMP是单串匹配。我们可以将它理解为在一个模式串上由失配指针fail[]组成的自动机。

多串情况下,我们可以把模式串建成一棵Trie树。

getfail()时用bfs维护fail指针。

引入last[],表示沿fail向回跳时遇到的第一个单词节点。


Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
const int N = 1000010,C = 26;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct ACAutomaton
{
int ch[N][C],f[N],last[N],val[N],sz;
std::queue<int> Q;
inline void init()
{
#define cl(a) memset(a,0,sizeof(a))
cl(ch);cl(f);cl(last);cl(val);sz = 0;
}
ACAutomaton(){init();}
inline void insert(char *T,int a)
{
int l = strlen(T),u = 0;
for(int i = 0,c = T[0] - 'a';i < l;c = T[++i] - 'a')
{
u = (ch[u][c] = ch[u][c] ? ch[u][c] : ++sz);
}
val[u] = a;
}
inline void getfail()
{
Q.push(0);
while(Q.size())
{
int u = Q.front();Q.pop();
for(int c = 0,v = ch[u][c];c < C;v = ch[u][++c])
{
if(!v) {ch[u][c] = ch[f[u]][c];continue;}
f[v] = u ? ch[f[u]][c] : 0;
last[v] = val[f[v]] ? f[v] : last[f[v]];
}
}
}
inline void query(char *T,int *ret)
{
int l = strlen(T),u = 0;
for(int i = 0,c = T[0] - 'a';i < l;c = T[++i] - 'a')
{
u = ch[u][c];
if(val[u]) ret[val[u]]++;
int v = u;while(v = last[v]) if(val[v]) ret[val[v]]++;
}
}
}AC;
char A[160][160],B[N];
int ret[N];
int main()
{
int n;
while(n = getint())
{
AC.init();
memset(A,0,sizeof(A));memset(B,0,sizeof(B));
for(int i = 1;i <= n;i++) {scanf("%s",A[i]);AC.insert(A[i],i);}
AC.getfail();
scanf("%s",B);AC.query(B,ret);
int mx = 0,cnt = 0;for(int i = 1;i <= n;i++)
{
if(ret[i] > mx) mx = ret[i],cnt = 1;
else cnt++;
}
printf("%d\n",mx);
for(int i = 1;i <= n;i++) if(ret[i] == cnt) printf("%s\n",A[i]);
}
return 0;
}