开个坑，待补
SAM
SAM 是一个接受 $s$ 的所有后缀的 $DFA$，从初始状态 $t_0$ 出发走到一个终止状态，则路径上所有转移连接起来一定是 $s$ 的一个后缀。一个很显然的性质是 SAM 包含了 $s$ 的所有子串，因为子串可以视为后缀的前缀。
然后我们引入一些概念。
$\operatorname{endpos}$ 和等价类
我们定义 $\operatorname{endpos}(t)$ 为字符串 $s$ 中 $t$ 的所有结束位置集合，对于两个 $\operatorname{endpos}$ 集合相等的子串 $t_1, t_2$ 我们称它们属于一个等价类 $E$。
换句话说，SAM 中的每个状态对应一个或多个 $\operatorname{endpos}$ 相同的子串。
接下来是一堆引理，都比较显然，感性理解一下。
引理 $1$ ：
考虑两个非空子串 $s_1, s_2$，令 $|s_1|\geq|s_2|$。
$1.1$ ：若 $s_1,s_2$ 的 $\operatorname{endpos}$ 相同，那么 $s_2$ 是 $s_1$ 的一个后缀，且 $s_2$ 在 $S$ 中每一次都以 $s_1$ 的后缀的形式出现。
$1.2$：若 $s_2$ 是 $s_1$ 的一个后缀，且 $s_2$ 在 $S$ 中每一次都以 $s_1$ 的后缀的形式出现，那么 $s_1,s_2$ 的 $\operatorname{endpos}$ 相同。
引理 $2$：
考虑两个非空子串 $s_1, s_2$，令 $|s_1| \geq |s_2|$
$2.1$：若 $s_2$ 是 $s_1$ 的一个后缀，则有 $\operatorname{endpos}(s_1) \subseteq \operatorname{endpos}(s_2)$。
$2.2$：若 $s_2$ 不是 $s_1$ 的一个后缀，则有 $\operatorname{endpos}(s_1) \cap \operatorname{s_2} = \varnothing$
引理 $3$：
一个 $\operatorname{endpos}$ 等价类不会包括两个本质不同而长度相同的字符串。
引理 $4$：
$4.1$ 一个 $\operatorname{endpos}$ 等价类 $E$ 中的任意两个子串，要么相同，要么较短者为较长者的真后缀
$4.2$ 设 $l, r$ 分别为 $E$ 内包含最短和最长子串的长度，则 $\cup |E_i| = {l \leq x \leq r, x \in N^{*}}$
后缀链接
考虑 SAM 中某个不是初始状态的状态 $v$，定义 $w$ 为 $v$ 对应等价类中最长的一个字符串，则 $v$ 的后缀链接要连接到字符串 $t$ 的等价类 $u$ 上并且满足 $t$ 为最长的，与 $w$ 不在同一个等价类的 $w$ 的一个真后缀。
它的实际意义在于根据引理 $4.2$，如果从某个等价类 $E$ 不断跳 $\operatorname{link}$ 直到初始结点的途中一定可以访问到 $E$ 中最长子串 $w$ 的每一个后缀。
引理 $5$：
设一个 $\operatorname{endpos}$ 等价类为 $E$，$E$ 中最短的串为 $s$.
$5.1$ ：$link(E)$ 中最长的串是 $s$ 长度为 $|s| - 1$ 的后缀。
$5.2$ ：$E \subsetneq link(E)$
其中 $5.1$ 转化为：
$\operatorname{short}(E) = \operatorname{long}(\operatorname{link}(E)) + 1$，其中 $\operatorname{short}$ 表示最短， $\operatorname{long}$ 表示最长。
引理 $6$：
所有后缀链接构成一棵根节点为 $t_0$ 的树。
这是（@ZTer）大佬博客里的一张图。
构造
在构造之前我们先定义一些记号。
对于每一个结点 $v$ ，它对应一个等价类 $E$ 。我们记 $\operatorname{long}(v)$ 为 $E$ 中最长的串，$\operatorname{len}(v)$ 为其长度；$\operatorname{short}(v)$ 为 $E$ 中最短的串，$\operatorname{minlen}(v)$ 为其长度。那么 $E$ 中每个串都是 $\operatorname{long}(v)$ 的后缀，且所有字符串的长度的并集为 ${\operatorname{minlen}(v)≤x≤\operatorname{len}(v),x∈N^{*}}$。
其中 $\operatorname{minlen}(v) = \operatorname{len}(\operatorname{link}(v)) + 1$。
同时根据上述引理 $3$ 和 $4.2$，我们可以得出从任意结点 $v_0$ 顺着后缀链接遍历，总可以访问到 $P$。途中会访问到若干结点 $v_i$ ， $v_i$ 中包含的字符串的长度恰好覆盖一段区间 $[\operatorname{minlen}(v_i),\operatorname{len}(v_i)]$ 的每一个整数，并且每一个 $v_i$ 恰好覆盖的区间都不相交，这些区间的并为 ${0≤x≤\operatorname{len}(v_0),x∈N^{*}}$。
接下来是构造的算法流程：
SAM 中的每个点需要维护一个 $len$ 和一个 $link$，以及出边。
最初 SAM 中只有一个状态 $t_0$，编号为 $0$，其中 $t_0$ 的 $len = 0, link = -1$。令 $last$ 为当前已经做完的字符串 $S$ 所对应的结点，最初 $last = 0$，现在我们要添加一个字符 $c$.
- 创建一个新状态 $cur$，则 $\operatorname{len}(cur) = \operatorname{len}(last) + 1$.
-
从 $last$ 开始跳后缀链接，如果当前跳到的点 $v$ 没有出边 $c$ 就创建一条 $(v, cur)$ 的边 $c$.
-
如果走到了 $t_0$，那么 $\operatorname{link}(cur) = 0$，去 $7$.
- 如果当前结点 $v$ 有出边 $c$，令该结点为 $p$，它沿出边 $c$ 到达 $q$，然后分类讨论。
- 如果 $\operatorname{len}(q) = \operatorname{len}(p) + 1$，赋值 $\operatorname{link}(cur) = q$，转 $7$.
- 否则复制状态 $q$ 到新点 $copy$（信息包括 $\operatorname{link}(q)$ 与 $q$ 的出边），然后 $\operatorname{len}(copy) = \operatorname{len}(p) + 1$，$\operatorname{link}(q) = copy, \operatorname{link}(cur) = copy$。接着从 $p$ 出发遍历后缀链接，若遍历到有出边 $c$ 的点 $v$ 就重定向这条边为 $(v, copy)$。
- $last = cur$，结束
除了分类讨论其实都比较好懂。
$1$ 和 $2$ 部分是因为 $len(last) = S$，所以 $len(S + c) = len(last) + 1$。同时所有 $S$ 的后缀都可以添加一个 $c$ 成为 $S + c$ 的后缀，从而我们就达到记录每一个后缀的目的。
$3$ 部分也是显然的，重点来讲 $4, 5, 6$ 部分。
我们考虑 $long(p)$ 为 $S$ 的后缀，所以 $long(p) + c$ 一定是 $S + c$ 的后缀，又因为从 $S$ 跳 $link$ 时所经过的点的 $\operatorname{len}(p)$ 长度递减，所以对于 $cur$ 来说 $\operatorname{long}(p) + c$ 满足“最长、不等价、后缀”的后缀链接定义。所以 $\operatorname{long}(p) + c$ 就应该是 $\operatorname{link}(cur)$ 中的最长字符串。
但我们还不知道 $\operatorname{long}(p) + c$ 是否是 $q$ 中最长的字符串，所以要分两类讨论。
当 $\operatorname{len}(q) = \operatorname{len}(p) + 1$ 时就很显然了，我们考虑另一种情况。
由于 $q$ 中最长的字符串不是 $\operatorname{long}(p) + c$，所以我们需要一个 $\operatorname{long}(p) + c$ 为最长字符串的等价类。于是就有了 $copy$。$\operatorname{link}(cur) = copy$。
然后我们考虑新拆分出来的 $copy$ 实际上是从一个包含字符串的长度可以覆盖区间 $[\operatorname{minlen}(q), \operatorname{len}(q)]$ 中每一个整数的等价类 $q$ 中拆分出一个包含字符串的长度覆盖区间 $[\operatorname{minlen}(q), \operatorname{len}(p) + 1]$ 的等价类。所以分裂之后的新 $q$ 就应该覆盖 $(\operatorname{len}(p) + 1, \operatorname{len}(q)]$。
接着由于 $\operatorname{len}(\operatorname{link}(q)) = \operatorname{minlen}(q) - 1$，且 $\operatorname{len}(\operatorname{link}(copy)) = \operatorname{minlen}(q) - 1$，所以 $\operatorname{link}(copy) = \operatorname{link(q)}$。同时 $\operatorname{minlen}(q) - 1 < \operatorname{len}(p) + 1$，所以 $\operatorname{long}(copy)$ 才是 $\operatorname{long}(q)$ 的“最长、不等价、后缀”即后缀链接，所以 $\operatorname{link}(q) = copy$
除此之外，由于原先的 $q$ 变为了新 $q$，所以还需要重定向一些边，显然只有 $\operatorname{long}(p)$ 的后缀加上 $c$ 才会连向 $copy$。
时间和空间
时间复杂度为 $O(nlog|\sum|)$，因为要用 $map$ 维护出边。如果字符集大小足够小可以直接使用 $int$ 就是线性的了。
SAM 的结点数不会超过 $2n - 1$，边数不会超过 $3n - 4$ 所以要注意数组大小。
模板
namespace SAM {
struct state {
int len, link, f;
map<char, int> ne;
} st[N << 1];
int tot, last;
vector<int> g[N << 1];
void init() {
st[0].len = 0, st[0].link = -1;
tot = 0, last = 0;
}
void extend(char c) {
int cur = ++ tot;
st[cur].len = st[last].len + 1;
st[cur].f = 1;
int p = last;
while (p != -1 && !st[p].ne.count(c)) {
st[p].ne[c] = cur;
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].ne[c];
if (st[q].len == st[p].len + 1) {
st[cur].link = q;
} else {
int clone = ++ tot;
st[clone].len = st[p].len + 1;
st[clone].link = st[q].link;
st[clone].ne = st[q].ne;
while (p != -1 && st[p].ne[c] == q) {
st[p].ne[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
};
