后缀自动机（Suffix Automation, SAM）是一种能够接受所有源串后缀的最简的DFA（确定性有限状态自动机）．他的定义使得他具有以下性质：
- 最简
- 是一个有向无环图（DAG），点之间的单向边即为字符的转移
- 有且仅有源串的所有子串可以在这张图上走到一个节点，一个节点可能对应多个子串，这些子串的各个结束位置均完全一致
（这些字符串接下来的任何转移均完全相同．为了最简，这些状态会被合并）
- 时间、空间复杂度均在\(O(n)\)级别（这个需要证明）
如非特殊说明，下文中一切下标均从\(1\)开始．
定义
- 我们把代表任意空串的开始节点叫做\(\text{root}\)节点．
- 我们定义一个子串的\(\text{Right}\)集合表示他在源串中出现时的所有结束位置所组成的集合．
- 可能有多个子串能够同时到达一个节点，他们的\(\text{Right}\)集合一定完全相同．我们定义一个节点的\(\text{Right}\)集合为这个集合．
定义\(\text{root}\)的\(\text{Right}=\{1,2,3,\cdots,Len\}\)，即空串在所有地方都出现． - 我们定义一个（不是\(\text{root}\)）\(u\)节点的上级节点\(v\)（称为\(\text{Prev}\)）为满足\(\text{Right}(v)\supsetneqq\text{Right}(u)\)且\(\text{Right}\)集合最小的结点．
- 观察发现（接下来就会观察），一个节点表示的许多子串一定是某个子串的长度连续的后缀（接下来再来理解），我们称其中的最长长度为\(\text{MaxLen}\)，最短长度为\(\text{MinLen}\)
- 最后再定义\(\text{Step}\)为从根节点到一个节点的步数．
我们接下来举一个例子，以便理解：\[\large\text{qaq}\color{Blue}\underbrace{\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}}\color{Black}\text{ov}\color{Fuchsia}\overbrace{\color{Fuchsia}\text{o}\color{Blue}\underbrace{\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}}}\color{Black}\text{qwq}\color{OrangeRed}\text{efg}\]
在上面的例子中，蓝色的\(\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}\color{Black},\color{Blue}\text{cd}\color{OrangeRed}\text{efg}\color{Black},\color{Blue}\text{d}\color{OrangeRed}\text{efg}\)节点相同，他们的\(\text{Right}=\{9,18\}\)，大小是\(2\)．他们的子串长度\(\in\{4,5,6\}\)，所以对应节点有\(\text{MaxLen}=6,\text{MinLen}=4\)．我们称这个节点为\(p\)．
当子串进一步变小时，新的\(\color{OrangeRed}\text{efg}\)在其他地方也有出现，这使得\(\color{OrangeRed}\text{efg}\)的\(\text{Right}\)变大，变成了\(\{9,18,\color{OrangeRed}24\color{Black}\}\)．如果子串再继续变小，\(\text{Right}\)有可能继续变大，所以必须有一个新节点，称为\(q\)，并且有\(\text{Prev}(p)=q\)．这使得我们发现了一条规律：
- 节点\(\text{Prev}(u)\)对应的\(\text{MaxLen}\)长度恰为节点\(u\)的\(\text{MinLen}\)减\(1\)．
当子串向前变长时，新的\(\color{Fuchsia}\text{o}\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}\)出现的位置减少了，\(\text{Right}\)集合变成了\(\{18\}\)．同时，这个节点的\(\text{Prev}\)是\(p\)．
构造
SAM的构造采用增量法，即将源串的字符从左到右一个一个加到SAM中．现在考虑\(\text{SAM}(S)\)到\(\text{SAM}(S+c)\)的变化，其中\(S\)是字符串，\(c\)是新加入的字符．
首先，我们上一次加入的结点\(last\)代表了整个字符串，它一定会连向\(c\)，所以我们新建一个结点\(u\)，连到\(last\)的\(c\)字符出边中，且让\(\text{Step}(u)=\text{Step}(last)+1\)；在对\(last\)不断求\(\text{Prev}\)的过程中，只要当前节点没有\(c\)的出边，这个节点就需要向\(u\)连一条字符为\(c\)的出边．
如果我们在这个过程中一直走到了\(\text{root}\)都没有遇到出边\(c\)，那么这个新节点\(u\)的\(\text{Prev}(u)\)的子串只能是无所不在的空串了．\(\text{Prev}(u)\)置为\(\text{root}\)．（接下来的举例都是其上面的情况）\[\large\text{qwq}\color{Blue}\text{efgh}\color{Black}\text{q}\color{Blue}\text{efgh}\color{Black}\text{aq}\color{Blue}\text{efgh}\color{Fuchsia}\text{c}\]
如果遇到了有\(c\)出边的点，我们就称其为\(p\)，同时称\(p\)的\(c\)出边指向的节点为\(q\)．接下来有两种情况可供讨论：
如果\(\text{Step}(q)=\text{Step}(p)+1\)，那么之前出现的q和现在的\(p+c\)一定是一样的（\(p+c\)指从\(p\)节点向\(c\)边转移一步）．这样，我们直接把\(\text{Prev}(u)\)置为\(q\)即可．\[\large\text{qw}\overbrace{\color{Blue}\text{efgh}\color{BlueViolet}\text{c}}^{q}\color{Black}\text{ovo}\color{Blue}\text{efgh}\color{Black}\text{qaq}\color{Blue}\text{efgh}\color{Fuchsia}\text{c}\]
否则，\(q\)在\(p\)之前还会有其他在\(last\)中没有出现的字符，\(q\)和\(p+c\)一定不是等价的．在这种情况下，我们为\(p+c\)这个节点新建一个节点，称为\(v\)．\(v\)在子串的意义上是\(q\)的后缀，他的\(\text{Right}(v)=\text{Right}(q)+\{\text{Len}(S+c)\}\)（多了当前加进去的最后位置），所以我们应该把\(v\)的所有出边从\(q\)那里复制过来（当前源串的最后还没有出边），并且使得\(\text{Step}(v)=\text{Step}(p)+1,\text{Prev}(v)=\text{Prev}(q),\text{Prev}(q)=v\)，最后有\(\text{Prev}(u)=v\)．\[\large\underbrace{\color{Red}\text{ijkl}\color{Black}\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{BlueViolet}\text{c}}_{\color{Black}q}\color{Black}\text{qaq}\underbrace{\color{Red}\text{ijkl}\color{Black}\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{BlueViolet}\text{c}}_{\color{Black}q}\color{Black}\text{q}\overbrace{\color{Blue}\text{efgh}}^{p}\color{Black}\text{wq}\underbrace{\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{Fuchsia}\text{c}}_{v}\]
应用
我也不会啊……等会了再写