后缀自动机(SAM)

前述

后缀自动机（$Suffix Automaton$，简称 $SAM$ ）是一种用于字符串处理的有限状态自动机（ $DFA$ ）。
它能解决的问题（包括但不限于）：
1. 在另一个字符串中搜索一个字符串的所有出现位置。
2. 计算给定的字符串中有多少个不同的子串。

直观上，字符串的 $SAM$ 可以理解为给定字符串的 所有子串 的压缩形式。
然而，获得这么多的信息，其时空复杂度皆为 $O(n)$，可谓十分优秀。

本文只介绍后缀自动机的性质，且本文无图，因此本文不适用于 $SAM$ 零基础的人。

后缀自动机的性质

直观的看 $SAM$，其性质有：

1. 有一个源点，从源点到任意一个点经过的边可以形成一个字符串，其为原串的子串。
2. 字符串的 $SAM$ 可以理解为给定字符串的 所有子串 的压缩形式。
3. 从源点出发的路径不同，形成的子串不同。

$endpos$ 及其性质

$endpos$：也叫终点，考虑字符串 $s$ 的任意非空子串 $t$ ，我们记 $endpos(t)$ 为在字符串 $s$ 中 $t$ 的所有结束位置，本质是集合。
譬如：原串为 $abcab$，下标从 $1$ 开始，则 $endpos(ab) = [2, 5]$。

性质：
1. 不同子串的 $endpos$ 可能相同，也就是说一个 $endpos$ 集合会对应至少一个子串。
2. 对于 $SAM$ 中的每一个点（状态），其与 $endpos$ 一一对应，也就是说，不同点的 $endpos$ 不同。
3. 两个 $endpos$ 相同的子串，短串必为长串的后缀，若这两个子串长度相同，则这两个子串实为同一个子串。
4. 两个不同子串的 $endpos$只有两种关系，要么是包含或者被包含的关系，要么是交集为空集。
5. 任意两个子串 $s_1$ 和 $s_2$，不妨设 $len(s1) \geq len(s2)$，则
$s_2$ 是 $s_1$ 的后缀 $\Leftrightarrow$ $endpos(s_1) {\subseteq} endpos(s_2)$
$s_2$ 不是 $s_1$ 的后缀 $\Leftrightarrow$ $endpos(s_1) \cap endpos(s_2) = \varnothing$
6. 一个 $endpos$ 对应的子串的集合称为 $endpos$ 等价类，
记等价类中最长的子串为 $maxS$，最短的子串为 $minS$，则
对于等价类中任一子串 $S$， 其始终满足 $len(minS) \leq len(S) \leq len(maxS)$，也就是说，等价类对应的子串后缀相同，长度连续。

$Parent \space Tree$ ( $Link \space Tree$ ) 及其性质

$Parent \space Tree$ 是一颗树，树上的每个结点与 $SAM$ 上的结点对应，直观上可以理解为儿子结点是对父亲结点的 $endpos$ 的分割。
记儿子结点向父亲结点的边为 $Link$ 边。
注意：此处的 $len$ 与上文的 $len$ 不完全相同，此处的 $len$ 实为 $endpos$ 中最长串（$maxS$）的长度。

性质：
1. 令 $fa$ 为 $u$ 的父亲，则$minlen(u) = len(fa) + 1$，也就是说，结点 $u$ 的最小串是通过在结点 $fa$ 的最大串的最前面添一个字符得到的。
2. 沿着 $Parent \space Tree$ 的 $Link$ 向上走，是一个不停的缩小后缀，每往上一层，就会删去 $endpos$ 等价类中最短串的最前面的字符的过程。（这边建议在旁边放个图食用这句话）。
3. 集合可能在分割的时候丢失。
4. 因 $Parent \space Tree$ 上的所有结点都与 $SAM$ 上的结点对应，故此处也可证明 $SAM$ 上的点最多有 $2n$ 个。

后记

为啥要整理这些性质，主要是在于做题不是考察你的板子背的有多熟，而是考察你对算法的性质理解的深不深。就像 $AC$ 自动机可以通过某结点的 $fail$ 边与该结点连一条有向边构建出来的数据结构 $fail$ 树。
这颗 $fail$ 树上的结点既可以表示某个串的前缀（ $Trie$ 树的性质），也可以表示匹配串的后缀的前缀( $fail$ 指针本身的性质)。
因此父亲结点和儿子结点的关系有：父亲结点表示的前缀 是儿子结点表示的前缀 的后缀（ $fail$ 树的性质），可见要完全理解 $fail$ 树，你必须得深刻理解 $AC$ 自动机的各种性质。

应用不想写，摸了。