AC 自动机
前言
最近集训时将难一些的字符串题时发现自己似乎已经忘了，或者就根本没学懂过 AC 自动机，于是重学一遍。
——2025.6.11
功能
AC 自动机可以实现比 KMP 和 Trie 更多的字符串匹配方面的功能。比如求模式串是否在文本串中出现过，出现了多少次等。不同于 KMP，AC 自动机支持多模式串的匹配。可以认为，AC 自动机就是在 Trie 上进行 KMP，同样要求最长公共前后缀，只不过前缀可以从任意模式串中截取而非 KMP 的单一模式串。类似于 KMP 的 $nxt$ 数组，AC 自动机中称这个指针为 $fail$。
我们举个例子：若干模式串组成 Trie
为了防止过多 $fail$ 弄得图片过乱，我们只取一个例子：$9$ 节点处，我们发现有 $0$ 节点到 $2$ 节点和 $7$ 节点到 $9$ 节点的最长公共前后缀 he。所以，类似 KMP，$9$ 处的 $fail$ 应指向 $2$。
建树
那么，$fail$ 究竟应该如何构建呢？我们使用 BFS 来遍历 Trie，在失配时不断跳 $fail$。
build AC automaton
1 | inline void build(){ |
然而，这样一直跳 $fail$ 效率太低了。我们可以在一开始就预处理出不存在的边的 $fail$，将查找 $fail$ 优化至 $O(1)$。此时的 Trie 由树变为了图。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16inline void build(){
queue<int> q;
for(int i=0;i<26;i++)
if(nxt[0][i]) q.push(nxt[0][i]);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(nxt[u][i]){
fail[nxt[u][i]]=nxt[fail[u]][i];
q.push(nxt[u][i]);
}
else nxt[u][i]=nxt[fail[u]][i];
}
}
}
多模式串匹配
我们以本题的匹配为例，只需每次跳 $fail$ 并计数，打标记防止记重就好了。1
2
3
4
5
6
7
8
9
10inline int query(string s){
int u=0,res=0;
for(int i=0;i<(int)s.length();i++){
int c=s[i]-'a';
u=nxt[u][c];
for(int j=u;j&&ed[j]!=-1;j=fail[j])
res+=ed[j],ed[j]=-1;
}
return res;
}
效率优化
我们发现，匹配时一直在跳 $fail$，这个操作事实上是可以优化的。
显然，一个 AC 自动机上的 $fail$ 边应当会构成一棵内向树。因此可以进行拓扑排序优化。
按照拓扑序处理节点，累加出现次数。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
using namespace std;
constexpr int N=2e5+10;
int nxt[N][26],tot,fail[N],n,ed[N],ans[N],indegree[N],mp[N];
inline void insert(string s,int id){
int u=0;
for(int i=0;i<(int)s.length();i++){
int c=s[i]-'a';
if(!nxt[u][c]) nxt[u][c]=++tot;
u=nxt[u][c];
}
++ed[u];
mp[id]=u;
}
inline void build(){
queue<int> q;
for(int i=0;i<26;i++)
if(nxt[0][i]) q.push(nxt[0][i]);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(nxt[u][i]){
fail[nxt[u][i]]=nxt[fail[u]][i];
++indegree[nxt[fail[u]][i]];
q.push(nxt[u][i]);
}
else nxt[u][i]=nxt[fail[u]][i];
}
}
}
inline void topo(){
queue<int> q;
for(int i=0;i<=tot;i++) if(!indegree[i]) q.push(i);
while(!q.empty()){
int u=q.front();
q.pop();
int v=fail[u];
ans[v]+=ans[u];
if(!--indegree[v]) q.push(v);
}
}
inline void query(string s){
int u=0;
for(int i=0;i<(int)s.length();i++){
int c=s[i]-'a';
u=nxt[u][c];
ans[u]++;
}
}
string s,t;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>s,insert(s,i);
build();
cin>>t;
query(t);
topo();
for(int i=1;i<=n;i++)
cout<<ans[mp[i]]<<'\n';
return 0;
}
习题
[POI 2000] 病毒
建立 AC 自动机时判断，若某串的最长前缀是病毒，则它本身一定不合法。之后 dfs 判环就行，注意使用标记数组保证 dfs 的复杂度正确。代码有点丑陋，为了卡常写了循环展开。
code
1 |
|
[NOI2011] 阿狸的打字机
code
1 |
|
图片来源：