后缀自动机

后缀自动机可以简单地理解成是点数最小的自动机，满足这个自动机可以识别任何一个 $S$ 的子串。

$\text{endpos}$ 等价类

对于 $S$ 的一个子串 $T$，称 $T$ 的 $\text{endpos}$ 集合为 $S$ 中所有出现 $T$ 的结尾位置。两个 $T$ 是等价的当且仅当它们的 $\text{endpos}$ 集合是相同的。

根据后缀树，可以意识到这个东西和 $\text{startpos}$ 等价类是一样的，所以这个玩意也是最多 $2n-1$ 个（$n$ 充分大）。

同样的，一个 $\text{endpos}$ 等价类也由 $[mn,len]$ 表示，即所有位置向前延申 $[mn,len]$ 的长度都在这个等价类里。

显然，你往一个等价类里面扔一个前缀会得到另外一个等价类。

后缀链接

我们把每一个 $\text{endpos}$ 等价类退掉一个前缀得到的新等价类作为这个等价类的父节点，连接父子节点的边叫做后缀链接，简称树边。

转移

把一个 $\text{endpos}$ 等价类增加一个字符可以得到另一个新的等价类，这种边称为转移，也叫 DAG 边。

根据后缀自动机的性质，转移起点等价类中所有字符串加这个字符都可以转移到终点等价类，但终点等价类可能并不仅只包含这些字符串。

转移最多只有 $3n-4$ 个（假设 $n$ 充分大）

不会证明。

$\text{Blumer}$ 算法

流程

这个算法是一个用来构造后缀自动机的方法。

算法以一个空自动机（仅有开始节点 $1$ 构成）起始，通过增加末尾字符得到整个后缀自动机。

首先，让我们假设已经构造了前 $n-1$ 个节点的后缀自动机，现在正准备添加第 $n$ 个字符 $c$。

让我们令 $S[1,n-1]$ 所在的等价类为 $las$，这个等价类增加 $c$ 之后一定会得到一个新的等价类，记作 $x$，注意到下一次增量的时候 $las=x$。

同时，我们也发现增加 $c$ 在原串上意味着增加了恰好 $n$ 个后缀，那么接下来我们需要去枚举所有可以转移到 $S[i,n]$ 的节点，是哪些呢？根据后缀链接的定义，显然是 $las$ 的所有父节点。

于是我们枚举所有的 $las$ 的父节点，并把它们连到 $x$ 上。最后，$las$ 会跳到 $1$，此时 $x$ 的后缀链接就会指向 $1$。

看起来一切都很美好，但是我们随即发现了问题，当 $las$ 的某个父节点已经有指向 $c$ 的儿子怎么办？假设我们记这个儿子为 $y$。

考虑这个儿子是什么东西，它意味着 $S[i,n]$ 这个字符串在之前已经出现在某一个等价类里了，而这个等价类恰好就是 $y$。

此时我们需要做一个特判，当 $y$ 的最长子串就是这个后缀里的子串的时候，那么 $y$ 和它的父亲已经包含了剩下后缀的所有信息，我们直接将 $x$ 的后缀链接置向 $y$ 即可。

否则，我们会发现 $y$ 的最长后缀的 $\text{endpos}$ 集合不含有 $n$，但 $y$ 的最短后缀却包含 $n$（根据转移的性质）。所以我们需要把 $y$ 给分裂出一个 $z$，表示 $y$ 中较短后缀构成的 $\text{endpos}$ 集合，那么这个 $z$ 就是 $x$ 和 $y$ 的父边。

最后的最后，考虑所有原来转移到 $y$ 的转移，现在它们只能转移到 $z$ 了，这很显然。

检查一遍，没有疏漏，于是我们就完成了后缀自动机的构建。

时间复杂度

首先，对于所有加新边/新点的操作，其复杂度和后缀自动机的边数是相等的，都是 $O(n)$。

因此我们只需要证明最后一步，把所有转移到 $y$ 的转移重定向到 $z$ 这一步，但是我太菜了，不会。