后缀自动机
记号
- $\Sigma$ 表示字符集
- $\Sigma^\ast$ 表示这个字符集能构成的所有字符串
- $\lambda$ 表示空字符串
- $|w|$ 表示字符串 $w$ 的长度
- $w_i$ 表示字符串 $w$ 的第 $i$ 个字符。
- $xy$ 表示字符串 $x$ 与 $y$ 拼接得到的字符串
end-pos 函数
对于某个字符串 $w=a_1,\cdots,a_n\in\Sigma^\ast(a_1,\cdots,a_n\in\Sigma)$ 和 $t\in\Sigma^\ast$，$\operatorname{end-pos}_w(t)=\{i\mid t=a_{i-|y|+1}\cdots a_i\}$。特殊地，$\operatorname{end-pos}_w(\lambda)=\{0,1,2,\cdots,n\}$。不会混淆的情况下可以简记作 $\operatorname{end-pos}(t)$。
称字符串 $s$ 的两个子串 $x,y$ 右端点等价，当且仅当 $\operatorname{end-pos}_w(x)=\operatorname{end-pos}_w(y)$，记作 $x\overset w\equiv y$，简记作 $x\equiv y$。右端点等价显然是一种等价关系，于是我们可以将 $x$ 所在的等价类记作 $[x]_w$，简记作 $[x]$。
引理 1.1 显然：
- 在字符串右侧追加字符能够保持右端点等价关系，即 $x\equiv y\Rightarrow xz\equiv yz$
- 如果两个子串右端点等价，则其中一个为另一个的后缀
- 两个字符串 $xy$ 与 $y$ 右端点等价，当且仅当 $y$ 每次出现，$x$ 都紧接着出现在其左侧
- $x$ 是 $[x]$ 中最长的子串，当且仅当存在以下两种情况之一：$x$ 是 $s$ 的前缀；$x$ 在 $s$ 的两个位置出现时左侧紧邻不同的字符
如果 $x$ 为某个等价类中最长的子串，我们称 $x$ 代表该等价类。
有向无环字符串图（DAWG）
DAWG（Directed Acyclic Word Graph）$D_w$ 定义为满足以下条件的有限状态自动机：
- 字符集为 $\Sigma$
- 状态与 $s$ 中的右端点等价类一一对应
- 转移为 $[x]\overset a\to[xa]$，其中 $xa$ 为 $w$ 的子串（注意到右端点等价具有右复合不变性，这保证了某个状态对于某个字符的转移是唯一的）
- 起始状态为 $[\lambda]$
- 每一个状态都是接受状态
下文混用“状态”与“右端点等价类”两种说法。
引理 1.2 $D_w$ 能够识别 $w$ 的所有子串。
证明： 构成 $D_w$ 的接受状态的右端点等价类的并即该字符串的所有子串，由 Nerode 定理易证。$\Box$
DAWG 不一定是能够识别 $w$ 的所有子串的最小 DFA。
后缀自动机（SAM）的性质
SAM（Suffix Automaton）$S_w$ 定义为，在 $D_w$ 的基础上，将接受状态改为所有后缀所在的等价类，即 $\operatorname{end-pos}$ 值包括 $|w|$ 的所有等价类。
定理 1.3 对于任意 $w\in S^\ast$，$S_w$ 是最小的能够识别 $w$ 所有后缀的有限状态自动机
证明： 由定义，$S_w$ 所有接受状态的并集即 $w$ 的所有后缀，所以 $S_w$ 能够识别 $w$ 的所有后缀。欲证明最小性，不难发现对于任意 $x\equiv y$ 和 $z\in\Sigma^\ast$，$xz$ 是 $w$ 后缀当且仅当 $yz$ 是 $w$ 后缀，于是由 Nerode 定理易证。$\Box$
如果两个子串的 $\operatorname{end-pos}$ 集合有交，那么其中一个一定是另一个的子串，于是前者的 $\operatorname{end-pos}$ 值是后者的 $\operatorname{end-pos}$ 值的超集。所以某个字符串 $w$ 的所有等价类能够由此关系构造一棵有根树，使得 $\operatorname{end-pos}(u)$ 是 $\operatorname{end-pos}(v)$ 的超集当且仅当 $u$ 在树上为 $v$ 的祖先。下文把这棵树称作 parent 树 $T(w)$。
定理 1.4 如果 $x$ 在 $w$ 中代表某个等价类 $[x]$，那么 parent 树上该等价类的子节点为 $[ax]$，其中 $a\in\Sigma$，且 $ax$ 在 $w$ 中至少出现过一次。
证明 根据定义，$[x]$ 在 $T(w)$ 上子节点对应的 $\operatorname{end-pos}$ 为所有极大的合法的 $\operatorname{end-pos}(x)$ 的真子集，即一定能够表示为某个 $\operatorname{end-pos}(ax)$，其中 $a\in\Sigma$。$\Box$
由定理 1.4，$T(w)$ 为 $w$ 反串的后缀树。
引理 1.5 对于长度大于等于 $2$ 字符串 $w$，$S_w$ 最多有 $2|w|-1$ 个状态。
证明 特别地，对于 $w=a^n$（$n>2$），$S_w$ 有 $n+1$ 个状态。否则我们将 $T(w)$ 上的所有节点分类讨论。
如果某个子串 $x$ 在 $w$ 中两个位置出现时左侧紧邻不同字符，那么 $[x]$ 至少有两个子节点。因此根据引理 1.1 的 4，只有 $0$ 个或 $1$ 个子节点的等价类的代表元一定是 $w$ 的前缀。因为某个前缀只能出现在一个等价类中，并且由于 $w$ 由至少两种字符构成，$[\lambda]$ 至少有 $2$ 个子节点，所以有 $0$ 个或 $1$ 个子节点的等价类不多于非空前缀，所以最多有 $|w|$ 个。
而因为树的性质，至少有 $2$ 个子节点的节点个数少于总节点数的一半，所以总节点数少于有 $0$ 个或 $1$ 个子节点的节点个数的两倍，即最多有 $2|w|-1$ 个。$\Box$
$S_w$ 节点数达到此上界，当且仅当 $w=ab^n$，其中 $a\not=b$，在此不做证明。
引理 1.6 对于长度大于等于 $2$ 的字符串 $w$，$S_w$ 的转移边数最多比状态数多 $|w|-2$。
证明 对于 $S_w$ 的任一生成树，其树边比状态数少 $1$。而对于每一条非树边 $(p,q)$，都可以构造出至少一条从 $[\lambda]$ 到 $[w]$ 的路径，使得该非树边为路径中第一条非树边。具体构造方案为：在生成树上从 $[\lambda]$ 到 $p$，从 $p$ 到 $q$，因为 $S_w$ 上仅有 $[w]$ 一个点出度为零并且图上无环，所以至少存在一条从 $q$ 到 $[w]$ 的路径。因为 $w$ 有 $|w|-1$ 个后缀经过了至少一条非树边，每个后缀对应唯一一条从 $[\lambda]$ 到 $[w]$ 的路径，所以非树边最多有 $|w|-1$ 条。于是有 $S_w$ 的转移边数最多比状态数多 $|w|-2$。$\Box$
结合引理 1.5 和引理 1.6 有如下结论。
定理 1.7 对于长度大于 $2$ 的字符串 $w$，$S_w$ 的状态数最多为 $2|w|-1$，转移边数最多为 $3|w|-4$。
证明 由引理 1.6，转移边数不超过状态数加 $|w|-2$。因此转移边数一个较松的上界为 $3|w|-3$。转移边数达到这个上界，仅当状态数达到 $2|w|-1$ 的上界，即 $w$ 形如 $ab^n$，此时转移边数为 $2|w|-1$，无法达到该上界。因此转移边数的上界为 $3|w|-4$。
达到该上界当且仅当 $w=ab^nc$，其中 $a,b,c$ 两两不同。
构建 SAM 的在线算法
考虑对从短到长每个前缀依此建出其对应的 SAM。于是只需要考虑一个字符串末尾加入某个字符后 SAM 的变化即可。