（注：本篇博客可能讲的非常垃圾，还和 OI-wiki写的长得很像，所以仅供参考，如果我讲不懂的话把谭老师讲的 SA 搞懂就行了，我们相信谭老师讲的一定非常好！

证明，例子和代码先咕了，进度可能还差得远得很（后面有时间再补。。

后缀自动机（SAM）

前置约定

字符串从 \(0\) 开始计数。字符串或集合 s 的符号 \(|s|\) 表示 \(s\) 的大小。

定义

一个字符串 \(s\) 的 SAM 是一个能接受 \(s\) 的所有后缀的最小的 DFA（确定性有限自动机或确定性有限状态自动机）。

不需要知道什么是 DFA ，你只需要知道：

• SAM 是一个 DAG ，其中每个节点是一个状态，状态内是一个字符子串，边是状态间的转移，转移都是一个字符，注意每个状态所有出边没有重复。

• 整张图存在一个源点 \(\tau\) ，称为初始状态，其他所有状态都能经由初始状态到达。

• 存在一个或多个终止状态，如果从初始状态出发，到一个终止状态为止，路径上所有转移连接起来是原字符串 \(s\) 的一个后缀，可能会有多条路径，但是同样适用。

• 在所有满足上述条件中，SAM 是节点数最少的（这个可以选择性看不到）

性质夹概念

概念-结束位置 \(endpos\)

考虑一个 \(s\) 的一个非空字串 \(t\) ，我们计 \(endpos(t)\) 表示字符串 \(t\) 在 \(s\) 中出现的所有结束位置。

概念-等价类

因为两个非空字串 \(t_1\) 和 \(t_2\) 有可能存在 \(endpos\) 相等的情况，对于每种不同的 \(endpos\) 称所有 \(endpos\) 相等的字串组成的集合为若干个等价类。

引理 1

如果两个非空子串 \(t_1\) 和 \(t_2\) 的 \(endpos\) 完全相等，且规定前者大小更小，那么前者是后者的后缀，且只在后者中出现一次

引理 2

考虑两个非空子串 \(t_1\) 和 \(t_2\) ，且规定前者大小更小，那么当前者是后者的后缀，有： \(endpos(t_1) \supseteq endpos(t_2)\) ，否则，有： \(endpos(t_1) \cap endpos(t_2) = \emptyset\) 。

引理 3

考虑一个 endpos 的等价类，将集合中所有字符串按长度降序排列，其中没有长度相同的字符串，且后面的是前面的后缀，而且其长度的集合是一段连续的整数集合。

概念-后缀连接 link

考虑 SAM 中一个非 \(\tau\) 的状态 \(v\) ，设 \(u\) 为 \(v\) 对应的 endpos 中大小最大的那个。

然后考虑 \(u\) 中所有后缀，取长度最长的一个不和 \(u\) 在同一个等价类的字符串 \(w\) ，将 \(v\) 的 link 连向 \(w\) 。

注意，不可能不存在这样的 \(w\) ，因为还有空集，也就对应了初始状态 \(\tau\) 。

引理 4

所有后缀连接反向之后构成一颗以 \(\tau\) 为根的树。

引理 5

通过 \(endpos\) 集合构造的树（每个子节点的集合都包含在父节点的集合中）与通过 \(link\) 构造的树相同。

概念-parent树

没毛用。。不管他

一些必要的符号

我们设 longest(v) 表示一个等价类中最长的那个字符串， len(v) 为其长度；记 shortest(v) 为等价类中最短的那个字符串， minlen(v) 为其长度。

引理 3：这个等价类所有字符串的长度覆盖了区间 \([minlen(v), len(v)]\) 中的每个整数。

后缀连接 link： \(minlen(v) = len(link(v)) + 1\) 。

构造 SAM

首先，这是一个在线的算法，即每次逐个添加一个字符并维护当前 SAM 。

记 las 为添加新字符 c 前整个字符串对应的终止状态，然后创建一个新状态 cur ，易知 len(cur) = len(las) + 1 ，然后剩下的任务就是要解决 link 的问题。

我们从状态 las 开始往上用 link 跳，如果没有字符 c 的转移就添加，直到存在就停下，记为状态 \(p\)

situation1

如果 p 是 -1 ，那么说明这个字符 c 是首次出现，将 link 赋为初始状态 0 ，完成。

situation2

如果存在 p ，那么通过转移 c 到一个新状态 q 。如果有 len(q) = len(p) + 1 ，将 link 赋为 q ，完成。

situation3

如果不是，那么我们复制一遍 q ，创建为新状态 clone ，把 q 除了 len 的所有信息复制到 clone 上，并将 len(clone) 赋为 len(p) + 1 。然后将 cur 和 q 的 link 都指向 clone 。

最后我们要让 p 继续往上跳，假如有一个向 q 的字符 c 的转移，就重新定向到 clone 。

三种情况完了之后就可以更新 las 为 cur 就行了。