写在前面
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 |
|
例题解析
咕咕咕咕咕咕咕(
在写了在写了,别骂了别骂了