基于自动机理论的基础字符串算法选讲

字符串 AC自动机 回文自动机

自动机理论

一种抽象的离散数学系统模型，在OI中我们只关心它的应用。

有限状态自动机

OI中最常见的自动机模型。

五元组： $Q,\sum , \phi , q_0, F$

状态集合，字符集合，转移函数，起始状态，终止状态。

一个字符串从起始状态可以转移至某个中止状态，称为该串被这个自动机“接受”。

OI中应用的考虑

$Q$ ： 尽可能最简（ 通常$O(n)$ )

$q_0$ ：从空串出发

$F$：需要被识别的集合 / 识别失败

使得自动机可以接受所有可能的串。

AC自动机

出现于1975年

目的：识别文本串中的所有模式串。（查字典）

基于已知的字典串集合构建。

考虑一个最简单的自动机模型：目标是识别所有字典串。（判断输入串是否为某个字典串）

已学过的算法

其实trie树已经可以做到这一点了。

现在提高要求：识别文本串的每个子串。（识别所有可能的文本串，考虑每个子串是不是字典串）

考虑trie树的匹配过程，问题在于失配的时候怎么办。

倒回开头重新匹配？

重点：失配的时候应该怎么办

出现过的最长后缀！

$fail[x]$

如何求？

• fail 指向祖先
• 已知 x 的 fail，考虑如何求出 x 的每个儿子的 fail

匹配时注意字典串的包含关系，在 fail 树上DP一下即可。

经典题型

考虑到 fail 指针构成一棵树，可以在这棵树上套一些数据结构维护一些东西。
如 codeforces 163E，这类题目比较简单，可课后自行搜索相关题目。

另一种很经典的题型是在自动机上面跑DP，考虑到trans指针天然构成一种转移关系。

考虑长度为 $m$ 的所有由大写字母组成的字符串，对于给定的 $n$ 个字典串，只要出现其中任意一个这个串就是“可读的”，问有多少种不同的可读串。

Luogu P4052 [JSOI2007]文本生成器

首先考虑容斥，答案为 $26^m -$ 不可读的串的数量

对于后半部分，考虑 $dp_{i,j}$ 表示目前串生成了 $i$ 个字符，在自动机上走到了第 $j$ 个节点的方案数。

每个状态枚举下一个字符，转移到自动机的对应状态。需要注意的是不能访问任意的终止节点。

对于这类型的题目，通常形如对长度为 $n$ 的所有具有某种特殊性质的字符串进行计数，并且这种性质可以被自动机识别。这样通过建立自动机模型可以大幅降低状态数目。

回文自动机

考古：由俄罗斯人 Mikhail Rubinchik 于 2014 年的 Petrozavodsk Summer Camp 上首次提出。并很快在算法竞赛领域风靡起来。

类比AC自动机，考虑我们需要回文自动机做什么。

识别给定串的所有回文子串。

一个简单的引理：

$Lemma \ 1$ ： 一个长度为 $n$ 的字符串本质不同回文子串的个数是 $O(n)$ 的。

在这里我们接触一种常用的自动机构建方式：增量法构建。

实际上这是上文 AC自动机 构建方式的一种更形式化的表述。

首先对自动机的每个状态（节点）进行定义。

一个节点表示一个本质不同的回文子串，存储 fail, trans指针，len 表示串长。

下面考虑增量过程：

last 指针：自动机识别 $\text{pre}_{1,i}$ 的结果状态

考虑加入一个字符 $\text{x}$ 对状态的影响， trans or fail

fail：最长回文后缀

应用

最朴素的应用就是几乎完全替代 Manacher 算法。

Luogu P4762 [CERC2014]Virus synthesis

题目

AC自动机：

1. codeforces 163E
2. Luogu P6125 [JSOI2009]有趣的游戏 （需要一点点点概率与期望的知识）
3. codeforces 710F

PAM：

1. [Apio2014]回文串
2. luogu P4555 [国家集训队]最长双回文串
3. CodeForces 932G （比较复杂，用到周期与border那套理论的一些推论