0xfaner's Blog

Just something trivial

AC 自动机算法探究

Posted on In
Symbols count in article: 3.9k Reading time ≈ 4 mins.

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

写在前面

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

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

本文参考：OI-wiki，Menci’s Blog

前置知识及一些概念

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

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

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

例题解析

咕咕咕咕咕咕咕（

在写了在写了，别骂了别骂了