AC 自动机算法探究

本文探究了 AC 自动机算法及其基础应用

写在前面

AC 自动机是一种著名的多模匹配算法,在算法竞赛中有着非常重要的地位。

完成 SAM 的笔记后,0xfaner 抽空回顾了一下 AC 自动机的相关知识,并整理出了这篇博客。

本文参考:OI-wikiMenci’s Blog

前置知识及一些概念

AC 自动机,英文名 Aho-Corasick automaton,下文简称 ACAM。

要理解 ACAM ,需要具备 KMP 算法、字典树(英文名 Trie ,下文简称 Trie)和确定有限状态自动机(英文名 DFA,下文简称 DFA)的前置知识。Trie 需要读者自行了解,KMPDFA 在我其他博文中有过介绍。

ACAM 的定义

基于字符串集合 $\{s_1, s_2, \dots, s_n\}$ 的 ACAM 是一个接受且仅接受以 $s_i(1 \leq i \leq n)$ 为后缀的字符串的 DFA。

AC 自动机可以视作 Trie 和 KMP 的结合。

而从算法复杂度来看, ACAM 比 SAM 要简单一些,在大多数人看来 ACAM 是和 SAM 同等级的算法,这是从难度来看的。而实际上,ACAM是多模算法,SAM却是单模算法。

广义后缀自动机与后缀自动机的关系就是 AC 自动机与 KMP 自动机的关系。

这不难理解,因为 KMP 和 SAM 都是单模算法,ACAM 和 General-SAM 都是多模算法。

ACAM 的结构

ACAM 由两部分构成:Trie 图 和 fail 树。

这两部分共用相同的节点,区别在于连边不同。从另一个角度来看,fail 树就是在 Trie 的节点上建立失配指针形成的树。

下面将会分别介绍 Trie 图 和 fail 树。

Trie 图

第一阶段将所有的模式串插入到 Trie 中即可。

在第二阶段中,需要补足一些节点的转移边,让它们指向一些与它们的 fail 有关的节点。这部分将在 fail 树部分讲解机制和原理。

fail 树与失配指针

一些约定与性质

约定

做出一些约定,以避免歧义并使得陈述更加简短。

  • $str(i)$ 表示 Trie 中从根节点到节点 $i$ 的路径上的字符串

  • $fa(i)$ 表示 Trie 中节点 $i$ 的父节点

  • $dep(i)$ 表示 Trie 中节点 $i$ 的深度

  • $ch(i)$ 表示 $fa(i)$ 与 $i$ 所连的转移边的符号

失配指针

我们知道在 KMP 中有 $\pi$ 函数,用于求当前后缀的最长前后缀的长度,每次在位置 $i$ 匹配失败时需要返回到位置 $j$,记作 $\pi(i)=j$ 。

在 ACAM 中我们需要实现类似概念的 $fail$,也就是失配指针。记作 $fail(i)=j$,表示在节点 $i$ 匹配失败时需要返回到节点 $j$ 。

那么可以给出 $fail$ 的定义:

$fail(i)=\max\{j|str(j)\text{ is a suffix of }str(i) \And dep(j) < dep(i)\}$ 。

参照 KMP 对于 $\pi$ 函数的性质的讨论,我们可以得出一些结论:

第一个结论

$dep(fail(i)) \leq dep(fail(fa(i))) + 1$

我们知道 $dep(i)$ 不仅代表了节点 $i$ 的深度,也代表了 $str(i)$ 的长度。

假定存在节点 $i$ 满足 $dep(fail(i)) > dep(fail(fa(i))) + 1$

那么依据定义有 $str(fail(i))$ 是 $str(i)$ 的最长后缀,且 $str(fail(fa(i)))$ 是 $str(fa(i))$ 的最长后缀。

删去 $str(i)$ 末尾的一个字符,即得到 $str(fa(i))$,那么有 $str(fa(fail(i)))$ 也是 $str(fa(i))$ 的后缀。

依据定义可以推导出 $dep(fail(fa(i))) \geq dep(fa(fail(i))) \ (*)$

而依据假设有 $dep(fa(fail(i))) = dep(fail(i)) - 1 > dep(fail(fa(i)))$,这与 $(*)$ 相悖。

第二个结论

若有 $fail(fa(i)))$ 存在 $ch(i)$ 的转移边,记其转移到的节点为 $k$,则有 $fail(i)=k$

已知 $str(fa(k)) = str(fail(fa(i)))$ 为 $str(fa(i))$ 的后缀,那么 $str(k)$ 为 $str(i)$ 的后缀。

又有 $dep(k) = dep(fa(k)) + 1 = dep(fail(fa(i))) + 1$,结合第一个结论,不会存在比 $str(k)$ 更长的后缀。

所以有 $fail(i)=k$

最终结论

$fail(i)$ 可以被描述为 $fail(fail(fail(\dots)))$ 的结构,初始为 $fail(fa(i))$ 。记当前迭代到 $j$,那么当 $j$ 存在 $ch(i)$ 的转移边或 $j$ 为根节点时迭代停止。

我们需要找到深度最大的 $j$,以满足 $str(j)$ 是 $str(i)$ 的后缀。

通过第二个结论我们知道,深度最大的 $j$ 必然首先位于 $fail(fa(i))$ 的子节点。

如果 $fail(fa(i))$ 不存在这样的子节点,则问题转化为求深度最大的 $j’$,满足 $str(j’)$ 是 $str(fail(fa(i)))$ 的后缀。

这样我们发现,问题转化为不断迭代,初始 $j$ 为 $fail(fa(i))$,每次 $j$ 变为 $fail(j)$,直到 $j$ 存在 $ch(i)$ 的转移边或 $j$ 为根节点为止。

优化

观察 $fail(i)$ 的求解过程,每一个节点迭代过程中经过的节点数不确定,时间复杂度可能退化。因此需要优化求解过程。

我们知道 $fail(i)$ 的求解过程中,沿着 $fail$ 链不断转移的路径是固定的。那么我们可以预处理每一个节点沿着 $fail$ 链转移能到达的节点。

如果节点 $j$ 不存在 $ch(i)$ 的转移边,而以 $j$ 为出发点的 $fail$ 链上存在 $ch(i)$ 的转移边,记它们指向的最深的节点为 $k$,那么我们修改 Trie 的结构,给节点 $j$ 添加 $ch(i)$ 的转移边,让它指向 $k$ 即可。这样我们就得到了最终的 trie 图

利用 BFS 的方式进行遍历,利用递推关系进行赋值,这样可以将时间复杂度降低到线性。同时求解 $fail$ 时可以直接判断当前节点 $i$ 的父节点的 $fail$ 是否有 $ch(i)$ 的转移边即可,无需进行更多次的转移。

在代码实现中这种复杂的策略表现得很简单,下面会进行介绍。

算法策略及代码实现

算法策略

建立 Trie

首先将所有的模式串插入到 Trie 中,得到了 Trie 的第一阶段。

建立 fail 树与 Trie 图

按照 BFS 的方式从根节点开始遍历,假设当前遍历到节点 $i$,现在需要完成三件事:

给 $fail(i)$ 加入子节点 $i$

注意这里不是在修改 Trie ,而是在建立 fail 树

给 $i$ 能转移到的节点建立 $fail$

用 $j$ 来代表 $i$ 的某一个子节点,那么有 $fail(j)$ 为 $fail(i)$ 沿着 $ch(j)$ 转移到的节点。

补齐 $i$ 不存在的转移边

记该转移边对应的的符号为 $ch$,那么有该转移边指向 $fail(i)$ 沿着 $ch$ 转移到的节点。

代码实现

Luogu P3808【模板】AC自动机(简单版) 为例:

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
#include <bits/stdc++.h>
using namespace std;
#define N 1000007
int ch[N][26], occur[N], fail[N], num;
void insert(char *s) {
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++) {
int x = s[i] - 'a';
if (!ch[p][x]) ch[p][x] = ++num;
p = ch[p][x];
}
occur[p]++;
}
void getFail() {
queue<int> que;
for (int i = 0; i < 26; i++)
if (ch[0][i]) fail[ch[0][i]] = 0, que.push(ch[0][i]);
while (!que.empty()) {
int p = que.front();
que.pop();
for (int i = 0; i < 26; i++)
if (ch[p][i])
fail[ch[p][i]] = ch[fail[p]][i], que.push(ch[p][i]);
else
ch[p][i] = ch[fail[p]][i];
}
}
int query(char *s) {
int len = strlen(s), p = 0, ret = 0;
for (int i = 0; i < len; i++) {
p = ch[p][s[i] - 'a'];
for (int q = p; q && ~occur[q]; q = fail[q])
ret += occur[q], occur[q] = -1;
}
return ret;
}
int n;
char p[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", p);
insert(p);
}
getFail();
scanf("%s", p);
printf("%d\n", query(p));
return 0;
}

例题解析

咕咕咕咕咕咕咕(

在写了在写了,别骂了别骂了