Theme NexT works best with JavaScript enabled

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;
}

例题解析

咕咕咕咕咕咕咕(

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