AC自动机

发布时间: 2024-08-10 14:05:33

前置知识​

kmp，基础图论，Trie字典树

自动机基础 ​

首先理解一下自动机是用来干什么的：自动机是一个对信号序列进行判定的数学模型。

这句话涉及到的名词比较多，逐一解释一下。「信号序列」是指一连串有顺序的信号，例如字符串从前到后的每一个字符、数组从 1 到 n 的每一个数、数从高到低的每一位等。「判定」是指针对某一个命题给出或真或假的回答。有时我们需要对一个信号序列进行判定。一个简单的例子就是判定一个二进制数是奇数还是偶数，较复杂的例子例如判定一个字符串是否回文，判定一个字符串是不是某个特定字符串的子序列等等。

自动机的工作原理和地图很类似。假设你在你家，然后你从你家到学校，按顺序经过了很多路口。每个路口都有岔路，而你在所有这些路口的选择就构成了一个序列。

例如，你的选择序列是「家门 -> 右拐 -> 萍水西街 -> 尚园街 -> 古墩路 -> 地铁站 -> 下宁桥」，那你按顺序经过的路口可能是「家 -> 家门口 -> 萍水西街竞舟北路口 -> 萍水西街尚圆街路口 -> 尚园街古墩路口 -> 古墩路中 -> 三坝地铁站 -> 下宁桥地铁站」。可以发现，上学的选择序列不止这一个。同样要去地铁站，你还可以从竞舟北路绕道，或者横穿文鼎苑抄近路。

而我们如果找到一个选择序列，就可以在地图上比划出这个选择序列能不能去学校。比如，如果一个选择序列是「家门 -> 右拐 -> 萍水西街 -> 尚园街 -> 古墩路 -> 地铁站 -> 钱江路 -> 四号线站台 -> 联庄」，那么它就不会带你去同一个学校，但是仍旧可能是一个可被接受的序列，因为目标地点可能不止一个。

也就是说，我们通过这个地图和一组目的地，将信号序列分成了三类，一类是无法识别的信号序列（例如「家门 -> ???」），一类是能去学校的信号序列，另一类是不能的信号序列。我们将所有合法的信号序列分成了两类，完成了一个判定问题。

既然自动机是一个数学模型，那么显然不可能是一张地图。对地图进行抽象之后，可以简化为一个有向图。因此，自动机的结构就是一张有向图。

而自动机的工作方式和流程图类似，不同的是：自动机的每一个结点都是一个判定结点；自动机的结点只是一个单纯的状态而非任务；自动机的边可以接受多种字符（不局限于 T 或 F）。

例如下面是判断一个二进制数是不是偶数的自动机

从起始结点开始，从高到低接受这个数的二进制序列，然后看最终停在哪里。如果最终停在红圈结点，则是偶数，否则不是。

如果需要判定一个有限的信号序列和另外一个信号序列的关系（例如另一个信号序列是不是某个信号序列的子序列），那么常用的方法是针对那个有限的信号序列构建一个自动机。这个在学习 KMP 的时候会讲到。

需要注意的是，自动机只是一个数学模型，而不是算法，也不是数据结构。实现同一个自动机的方法有很多种，可能会有不一样的时空复杂度。

形式化定义 ​

（请看jpg，太难打了）

OI 中常用的自动机 ​

字典树

字典树 是大部分 OIer 接触到的第一个自动机，接受且仅接受指定的字符串集合中的元素。

转移函数就是 Trie 上的边，接受状态是将每个字符串插入到 Trie 时到达的那个状态。

KMP 自动机

KMP 算法 可以视作自动机，基于字符串 s 的 KMP 自动机接受且仅接受以 s 为后缀的字符串，其接受状态为 |s|。

转移函数：

$\delta(i, c)=\begin{cases}i+1&s[i+1]=c\0&s[1]\ne c\land i=0\\delta(\pi(i),c)&s[i+1]\ne c\land i>0\end{cases}$

AC 自动机

AC 自动机 接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串。也就是 Trie + KMP。

后缀自动机

后缀自动机 接受且仅接受指定字符串的后缀。

广义后缀自动机

广义后缀自动机 接受且仅接受指定的字符串集合中的某个元素的后缀。也就是 Trie + SAM。

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

回文自动机

回文自动机 比较特殊，它不能非常方便地定义为自动机。

如果需要定义的话，它接受且仅接受某个字符串的所有回文子串的 中心及右半部分。

「中心及右边部分」在奇回文串中就是字面意思，在偶回文串中定义为一个特殊字符加上右边部分。这个定义看起来很奇怪，但它能让 PAM 真正成为一个自动机，而不仅是两棵树。

序列自动机

序列自动机 接受且仅接受指定字符串的子序列。

后缀链接

由于自动机和匹配有着密不可分的关系，而匹配的一个基本思想是「这个串不行，就试试它的后缀可不可以」，所以在很多自动机（KMP、AC 自动机、SAM、PAM）中，都有后缀链接的概念。

一个状态会对应若干字符串，而这个状态的后缀链接，是在自动机上的、是这些字符串的公共真后缀的字符串中，最长的那一个。

一般来讲，后缀链接会形成一棵树，并且不同自动机的后缀链接树有着一些相同的性质，学习时可以加以注意。

AC自动机 ​

(终于写到正题了QWQ)

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。 （PS：不是自动ac题目的意思啦）

解释

简单来说，建立一个 AC 自动机有两个步骤：

 基础的 Trie 结构：将所有的模式串构成一棵 Trie。

 KMP 的思想：对 Trie 树上所有的结点构造失配指针。
   

然后就可以利用它进行多模式匹配了。

字典树构建

AC 自动机在初始时会将若干个模式串丢到一个 Trie 里，然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie，该怎么建怎么建。

这里需要仔细解释一下 Trie 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边就是状态的转移。

形式化地说，对于若干个模式串n1,n2,n2...... , 将它们构建一棵字典树后的所有状态的集合记作 Q。

失配指针

在AC自动机中，我们常常构造又一个失配指针（fail）来辅助多模式串的匹配

状态 \itu 的fail指针指向另一个状态，\large \it v ，其中\it v \in /it Q，且 v 是 u 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。

fail 指针与 KMP 中的 next 指针相比：

共同点：两者同样是在失配的时候用于跳转的指针。

不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。 因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。

总结下来，AC 自动机的失配指针指向当前状态的最长后缀状态。

注意：AC 自动机在做匹配时，同一位上可匹配多个模式串。

构建指针

下面介绍构建 fail 指针的 基础思想：

构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。

考虑字典树中当前的结点 u，u 的父结点是 p，p 通过字符 c 的边指向 u，即 trie[p,\mathtt{c}]=u。假设深度小于 u 的所有结点的 fail 指针都已求得。

如果 \text{trie}[\text{fail}[p],\mathtt{c}] 存在：则让 u 的 fail 指针指向 \text{trie}[\text{fail}[p],\mathtt{c}]。相当于在 p 和 \text{fail}[p] 后面加一个字符 c，分别对应 u 和 fail[u]如果 \text{trie}[\text{fail}[p],\mathtt{c}] 不存在：那么我们继续找到 \text{trie}[\text{fail}[\text{fail}[p]],\mathtt{c}]。重复 1 的判断过程，一直跳 fail 指针直到根结点。

如果依然不存在，就让 fail 指针指向根结点。

如此即完成了 \text{fail}[u] 的构建。