后缀自动机

定义

$S$的后缀自动机是一种能识别所有$S$的子串的自动机类型的数据结构。
$s(w)$表示字串$w$对应的后缀自动机上的状态。
$tran(s,ch)$表示当前状态是$s$，接收新字符$ch$之后到达的状态。
$Trans(s,str)$表示当前状态是$s$，接收新字符串$str$之后到达的状态。
$Suf[i]$表示从$i$位置开始的后缀，即$S[i,\left|S\right|]$。
$Right(s)=\{r_1,r_2,…,r_m\}$表示$s$状态代表子串出现位置右端点集合。
$SC$树（也称后缀链接树、Parent树、link树等）即为$Right$集合包含关系形成的树。
$f(s)$表示状态$s$对应的$Right(s)$在$SC$树上的父节点。

最简状态后缀自动机

最优后缀自动机的状态数为$O(2n)$，转移数为$O(3n)$。
后缀自动机中，一个状态表示的是出现位置相同（右端点相同），但长度不同的一系列串。
不同的$Right$集合之间只有相离和真包含关系，形成一个树形结构，叶子节点是只有一个位置的集合，因此总共有$n$个节点，整棵树的节点数（状态数）就是$O(2n)$。
显然对于任意状态$s$，$MaxL[f(s)]=MinL[s]-1$，因此每个节点只需要记录$MaxL[s]$和$f(s)$，状态$s$能表示的串长度范围是$(MaxL[f(s)],MaxL[s]]$。
将每条非树边（转移）映射到后缀上，每个后缀最多只会被一条非树边映射到，因此转移的数量是$O(3n)$。

构造

考虑在线增量构造，首先创建一个根节点$root$，标号为$1$，$MaxL[1]=0$，$f(1)=0$。
然后在已经建出$S[1,i-1]$的后缀自动机的基础上加上$S[i]$建出$S[1,i]$的后缀自动机。
显然新增的$i$个子串是$S[1,i]$的所有后缀，首先$S[1,i]$肯定不在SAM里，需要新建一个状态$np$。
新状态有$trans$为空，$MaxL[np]=i$。
要找到$f(np)$，就要找到最长的$S[i-x+1,i]$，要求在$S[1,i-1]$中出现过。
由于$S[i-x+1,i]=S[i-x+1,i-1]+S[i]$，因此要找到$S[1,i-1]$的最长后缀，使得其所在的状态存在$S[i]$的转移。
这一过程需要枚举$S[1,i-1]$的所有后缀，即从$S[1,i-1]$所在的状态$p$开始向上遍历到$root$来实现。如果没有任何状态有$S[i]$转移，则$f(np)=root$。