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

写在前面

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

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

前置知识及一些概念

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自动机（简单版）为例：

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

例题解析

~~咕咕咕咕咕咕咕（~~

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

0xfaner's Blog

AC 自动机算法探究