字符串乱学

打算系统性地学习和复习一下字符串算法。

一些算法内容比较多会拆到别的文章里。

符号与约定

首先让我们形式化地定义一下字符串的各个概念。

字符集为一个建立了全序关系的集合，用符号 $\Sigma$ 来表示。其中的元素被称为字符。

字符串 $s$ 是一个由若干字符按顺序排列而成的序列。

下文默认字符串下标从 $1$ 开始。

定义 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。

定义 $\left|s\right|$ 为字符串 $s$ 的长度。

空串即为不包含任何字符，$\left|s\right| = 0$ 的字符串。

我们定义字符与字符、字符与字符串、字符串与字符、字符串与字符串之间的拼接表示将这两个字符或字符串按顺序拼在一起得到的字符串，写作 $s + t$ 或 $st$。$s^k$ 表示 $k$ 个 $s$ 拼接。

字符串 $s$ 的一个子串 $s_{[l, r]}$ 表示 $s_l, s_{l + 1}, \ldots s_{r}$ 按顺序连接得到的字符串，即 $s_l + s_{l + 1} + \ldots s_r$。特别地，当 $[l, r] = \varnothing$ 时表示空串。
字符串 $s$ 的一个子序列 是由 $s$ 中的某些字符按原先的顺序拼接得到的字符串。

字符串 $s$ 的后缀为从某个位置 $i$ 开始到 $s$ 的最后一个字符的子串，用 $\mathrm{suf}(s, i)$ 表示，即 $\mathrm{suf}(s, i) = s_{i, |s|}$。真后缀为不是其本身的后缀，空串为任意字符串的后缀。
字符串 $s$ 的前缀为从 $s$ 第一个字符开始到某个位置 $i$ 的子串，用 $\mathrm{pre}(s, i)$ 表示，即 $\mathrm{pre}(s, i) = s_{1, i}$。空串为任意字符串的前缀。

字典序：以第 $i$ 个字符作为第 $i$ 关键字进行大小比较。若字符串 $s_1$ 为字符串 $s_2$ 的前缀，则认为 $s_1 < s_2$。

回文串（Palindrome String） 为满足 $\forall 1 \le i \le \left|s\right|, s_i = s_{\left|s\right| - i + 1}$ 的字符串。

字典树（Trie）

对于若干个字符串，我们构建出一棵有根树，这棵树有如下性质：

• 每条边上有一个边权，是一个字符。
• 每个点向儿子连的边的边权互不相同。
• 按顺序拼接从根到某个点的路径上的边权，得到的串一定是给出的字符串中某些串的前缀。
• 根到叶子的路径对应的串一定是某个给出的串。

例如：对于字符串 aa，aba，ba，caaa，cab，cba，cc，我们可以构造出如下的树：

（图源 OI Wiki）

这棵树被称为 Trie。

考虑如何构造 Trie。
我们考虑每次插入一个字符串，动态维护 Trie 的形态。

具体地，每次从根开始遍历，并同时维护该字符串当前的字符，如果当前点已经有该字符的儿子，就直接走过去，否则新建一个节点。

void insert(string s) {
	int now = 0;
	for (char c : s) {
		int id = c - 'a';
		if (!trie[now][id]) trie[now][id] = ++tot;
		now = trie[now][id];
	}
	return ;
}

Trie 的大小是 $O(\sum s)$ 的。可以通过合并二度点的方式将大小缩小到 $O(n)$（即压缩 Trie）。

Trie 的基本应用是查询某个串是否在给出的字典中出现过或查询某个串是字典中多少串的前缀。

要实现如上操作需要在每个节点上维护以该点为前缀的串的个数以及该点是否为给出的串。

对 Trie 的先序遍历可以实现字符串排序。

Trie 的本质是一个接受且仅接受给定串的自动机。

可以将整数视为定长的二进制串然后构建 Trie，这种 Trie 被称为 01Trie，由于其拥有非常优秀的树形结构因此常被用来维护与二进制操作相关的信息，由于与字符串关系不大因此这里略去不讲。

例题：[NEERC2016] Binary Code

给定 $n$ 个 01 串，每个串有至多一位是未知的，可以填 0 或 1，求是否存在一种方案，使得任意一个字符串都不是其他串的前缀。若有解则输出方案。

$1 \le n \le 5\times 10^5$，字符串总长不超过 $5\times 10^5$。

TL: 2s, ML: 1GB

考虑两个串 $s_i, s_j$，如果一种填法不合法，相当于要求若 $s_i$ 填了某个字符则 $s_j$ 不能填某个字符。是一个 2-SAT 问题。

问题是如果两两比较连边的话复杂都是 $O(n^2)$ 的，无法接受。

由于是前缀关系，考虑建出 Trie 树。对于每个串，将两种填法都加到 Trie 中，这样两个点之间有边当且仅当他们是祖先关系，发现树边刚好可以满足这点限制，直接拿来用好了。

实际实现时需要注意一些细节。

Border 理论

link

Z 函数（Z Algorithm）

对于一个字符串 $s$，定义函数 $z(i)$ 为 $s$ 与 $\mathrm{suf}(s, i)$ 的最长公共前缀（Longest Common Prefix, LCP）的长度。特别地，$z(1) = 0$。

显然求 Z 函数有一个朴素的 $O(|s|^2)$ 暴力就是枚举每个位置然后暴力向后延伸。考虑优化这个暴力。

假设我们已经求出 $z(1), z(2), \ldots, z(i - 1)$，考虑如何根据这些信息求出 $z(i)$。
我们取出 $j + z(j)$ 最大的一个位置，若 $i < j + z(j)$，可以得到 $s_{[i, j + z(j))} = s_{[i - j + 1, z(j)]}$，因此 $z(i) \ge \min\{z(i - j + 1), j + z(j) - i\}$。
考虑每次以这个作为 $z(i)$ 的初值再暴力向后扩展。

看起来好像只是优化了常数？实际上若 $i \ge j + z(j)$ 或 $j + z(j) - i \le z(i - j + 1)$ 都会使 $j + z(j)$ 增加至少 $1$。而当 $i < j + z(j)$ 且 $j + z(j) - i > z(i - j + 1)$ 时一定有 $z(i) = z(i - j + 1)$，此时不会进行暴力扩展。因此总时间复杂度就是 $O(|s|)$。

参考代码如下：

// n is |s|.
for (int i = 2, j = 0; i <= n; i++) {
	if (i < j + z[j]) z[i] = min(z[i - j + 1], j + z[j] - i);
	while (i + z[i] <= n && s[i + z[i]] == s[1 + z[i]]) z[i]++;
	if (i + z[i] > j + z[j]) j = i;
}

如果你学过 SA 你会发现 Z 函数能求的东西 SA 都能求，所以 Z 函数屁用没有。

Z 函数可以用来加速字符串比较，比较常见的应用是在 DP 中优化时间复杂度，或者纯粹拿来求 LCP。

例题 1：NOIP2020 字符串匹配

给你一个字符串 $s$，求有多少种方式可以将 $s$ 分解成 $(AB)^kC$ 的形式，使得 $A$ 中出现奇数次的字符数不超过 $C$ 中出现奇数次的字符数。

多组数据，$1 \le T \le 5, 1 \le |s| \le 2^{20}$。

TL: 1s, ML: 512MB.

考虑枚举 $|AB|$，此时 $k$ 的取值个数就是 $\lfloor\frac{z(|AB| + 1) + |AB|}{|AB|}\rfloor$。

然后再考虑字符个数的限制，显然我们只要知道 $C$ 中出现奇数次的字符个数就能得到有多少种划分 $AB$ 的方法了。

容易发现 $ABAB$ 的结构对 $C$ 中出现奇数次的字符个数是没有影响的，因此考虑对 $k$ 的奇偶性分类讨论。
当 $k$ 是奇数时，$C$ 中出现奇数次的字符的个数等于 $\mathrm{suf}(s, |AB| + 1)$ 中出现奇数次的字符个数。
当 $k$ 是偶数时，$C$ 中出现奇数次的字符个数等于全串出现奇数次的字符个数。

然后就做完了，时间复杂度 $O(T|s||\Sigma|)$。

例题 2：ARC058F 文字列大好きいろはちゃん

给 $n$ 个字符串，从中选出若干个，按给定顺序拼接，要求总长恰好为 $k$，求字典序最小的串。

$1 \le n \le 2000, 1 \le k \le 10^4$，字符串总长不超过 $10^6$。

TL: 5s, ML: 750MB.

考虑朴素 DP：设 $dp_{i, j}$ 表示前 $i$ 个串总长为 $j$ 时字典序最小的串，直接来时空间都是 $O(nk^2)$ 的。

先对于每个 $i, j$ 求出 $dp_{i, j}$ 有没有可能成为最终答案，即用 $i$ 后面的串能不能拼出 $m - j$ 的长度，然后抛弃掉不能成为答案的状态。
接下来考虑对于 $j < k$，若 $dp_{i, j}$ 不是 $dp_{i, k}$ 的前缀，则较大的那个必然不会成为答案。
这样操作后对于同一个 $i$，所有有效的状态较小的一定是较大的前缀，这样我们对于每个 $i$ 只需要记录最长的一个串即可。

然后考虑转移，按 $j$ 从小到大转移。$dp_{i, j}$ 显然只能从 $dp_{i - 1, j}$ 和 $dp_{i - 1, j - |s_i|}$ 转移过来，比较一下得到 $dp_{i, j}$，然后维护有效的状态。

考虑用一个单调栈维护有效状态，比较当前最长的串和 $dp_{i, j}$：

• 若是 $dp_{i, j}$ 的前缀：直接把 $dp_{i, j}$ 放入栈中。
• 若比 $dp_{i, j}$ 小：$dp_{i, j}$ 无效。
• 若比 $dp_{i, j}$ 大：一直弹栈直到栈顶是 $dp_{i, j}$ 的前缀。

考虑这个过程中我们要支持什么串的比较，显然用到的所有串都是上一轮的最长串的某个前缀接上 $s_i$，将这两个串拼一起求 Z 函数即可实现 $O(1)$ 比大小。

时间复杂度 $O(nk + \sum |s_i|)$。

Manacher

Manacher 用于求一个字符串 $s$ 的所有回文子串，也等价于求每个回文中心对应的最长回文子串的长度。

长度为偶数的回文子串的回文中心是两个字符，比较难搞，考虑用一些方法将它变成长度为奇数的串。

对于字符串 $s = s_1 s_2 s_3 \ldots s_n$，将其变成 $\#s_1\#s_2\#s_3\#\ldots\#s_n\#$，这里 $\#$ 是一个不在 $s$ 字符集中的特殊字符，这样所有长度为偶数的回文子串的中心就变成了某个 $\#$，并且若现在求得的最长回文子串的长度为 $p$，则原串长度就是 $\lfloor\frac{p}{2}\rfloor$，即新串的「半径」。

朴素暴力就是直接来。考虑用类似 Z 函数的方法优化。设 $p_j$ 为以 $j$ 为回文中心的最长回文子串的半径，假设已经求出了 $p_1, p_2, p_3, \ldots, p_{i - 1}$，取 $j + p_j$ 最大的 $j$，若 $i \le j + p_j$，则有 $p_i \ge \min\{p_{2j - i}, j + p_j - i + 1\}$。以此为 $p_i$ 的初值，然后暴力扩展。

时间复杂度分析和 Z 函数类似，读者自证不难，这里不再赘述。

注意实现时一般在两端添加另外两个特殊字符以防止越界。

// t is the original string, n is |t|.
string s = "^#";
for (char i : t) s.push_back(i), s.push_back('#');
s.push_back ('@');
for (int i = 1, j = 0; i <= 2 * n + 1; i++) {
	if (i <= j + p[j]) p[i] = min (p[2 * j - i], j + p[j] - i);
	while (s[i - p[i] - 1] == s[i + p[i] + 1]) p[i]++;
	if (i + p[i] > j + p[j]) j = i;
}

例题：PKUSC2024 Day1T1 回文路径

给定一个 $2\times n$ 的网格，每个格子上有一个字符，你可以从任意格子开始，往右或往下移动，在任意格子结束。记录下经过的格子的字符组成的字符串，求最长的路径长度使得该串是回文串。

$1 \le n \le 10^5$。

TL: 1s, ML: 512MB.

先求出只在某一行的最长回文子串，然后考虑在某个地方拐弯。
不妨假设回文中心在第一行，在回文中心右侧拐弯。

如果拐弯要不劣于不拐弯，那么容易得出如果在 $p$ 处向下拐，则第一行 $p + 1$ 的后缀和第二行 $p$ 的后缀的 LCP 的右端点应当恰好是原回文串的右端点。

容易发现此时等价于在回文串右端点拐弯，因此对于每个原本的回文串，有唯一确定的拐点。之后就直接二分哈希即可。

后缀数组（SA）

咕。

自动机（Automaton）

OI 中自动机一般指确定性有限状态自动机（Deterministic finite automaton, DFA）。

DFA 由以下五部分组成：

• 字符集 $\Sigma$：该自动机能输入的字符。
• 状态集合 $Q$。其具体意义视具体情况而定。
• 起始状态 $start$：一个特殊的状态。$start \in Q$。
• 接受状态集合 $F$：一些特殊的状态。$F \subseteq Q$。
• 转移函数 $\delta(p, c)$：其有两个参数，其中第一个参数 $p$ 为一个状态，$c$ 为一个字符，返回值为一个状态。满足 $p \in Q, \delta(p,c ) \in Q, c \in \Sigma$。

一般来说，一个 DFA 可以用这五个部分描述。

DFA 用于识别字符串，及从起始状态 $start$ 开始，按照转移函数进行转移，若最后到达了一个接受状态，则称该自动机可以识别该字符串。

这里的转移是指：若当前状态为 $p$，识别到了第 $i$ 个字符，则转移到状态 $\delta(p, i)$。

但是显然并不是任何时候都可以转移的，因此我们特殊定义不存在的转移为 $\delta(p, c) = \mathrm{null}$。$\mathrm{null}$ 是一个特殊的状态，其不是起始状态也不是结束状态，并且有 $\forall c \in \Sigma, \delta(\mathrm{null}, c) = \mathrm{null}$。

DFA 可以视作一个有向图，状态为图上的点，转移为图上的边，转移对应的字符为边权。

下面会讲一些 OI 中常见的 DFA。

子序列自动机

咕。

KMP 自动机

咕。

AC 自动机（Aho-Corasick Automaton, ACAM）

咕。

后缀自动机（Suffix Automaton, SAM）

endpos

讲后缀自动机之前首先要讲一下 $\mathrm{endpos}$。

对于字符串 $s$ 的任意非空子串 $t$，我们定义 $\mathrm{endpos}(t)$ 为 $s$ 中所有 $t$ 出现的位置的最后一个字符的位置，即：$\mathrm{endpos}(t) = \left\{x \mid s_{x - \left|t\right| + 1, x} = t\right\}$。

我们会发现对于某些子串可能会出现 $\mathrm{endpos}$ 相同的情况。
我们定义所有 $\mathrm{endpos}$ 相同的子串组成的集合为一个等价类。

性质 1：一个等价类里的所有子串一定是其中最长的子串的连续的后缀。

原因显然。

我们定义一个等价类中最长的子串为该等价类的代表元。

性质 2：一个等价类中的子串 $t$，其每次出现都是以代表元的后缀的形式。

显然。

性质 3：对于任意两个非空子串 $u, v (\left|u\right| \le \left|v\right|)$，一定满足 $\mathrm{endpos}(v) \subseteq \mathrm{endpos}(u)$ 或 $\mathrm{endpos}(u) \cap \mathrm{endpos}(v) = \varnothing$。

因为若 $\mathrm{endpos}(u)$ 与 $\mathrm{endpos}(v)$ 有交，则必然满足 $u$ 是 $v$ 的后缀。

为了方便叙述，下文中用 $\mathrm{len}$ 表示一个等价类中代表元的长度。
另外，为了方便理解，不妨定义 $\mathrm{endpos}(\text{空串}) = \varnothing$，且空串自己组成一个虚拟的等价类。

link

我们定义一个等价类的 $\mathrm{link}$ 为 $\mathrm{len}$ 最长的 代表元是 该等价类代表元后缀 的等价类。若不存在这样的等价类，则认为其 $\mathrm{link}$ 为空串的等价类。
注意，空串的等价类是为了方便理解我自己定义的，所以其没有 $\mathrm{link}$。

性质 1：如果将等价类视为一个点，每个等价类的 $\mathrm{link}$ 视为边，则其构成一棵内向树。

原因显然：每个点只有一个出边，且最终都指向虚拟等价类，且虚拟等价类没有出边。

我们称之为后缀链接树，或 parent tree。

性质 2：每个等价类的 $\mathrm{endpos}$ 一定是其儿子等价类的 $\mathrm{endpos}$ 的并集的超集（根除外），并且当且仅当其代表元为 $s$ 的前缀时会多一个元素，其他情况下相等。

每个等价类的元素一定是该等价类的儿子的元素的后缀。且对于任意非前缀的子串，其每次出现一定会对应某个以其为后缀的子串出现。

定义

终于要来力！

SAM 是一个接受 $s$ 的所有后缀的最小的 DFA。
SAM 的状态集合为所有等价类，起始状态为空串的等价类，接受状态为 $s$ 所有后缀所在的等价类。
SAM 的转移 $\delta(p, c)$ 的定义为，在 $p$ 中每个子串后添加一个字符 $c$ 得到的所有字符串所在的等价类。这些新的子串的 $\mathrm{endpos}$ 一定相同，关于这一点的正确性可以通过后文的 SAM 的构建来理解。

在所有满足上述条件的自动机中，SAM 是最小的。

性质 1：从起始状态出发，到达某一状态，按顺序记录下经过的转移的字符，其构成 $s$ 的一个子串。反之，$s$ 的每一个子串也对应某条路径。

性质 2：从起始状态出发到达某一状态的所有路径构成的字符串就是该等价类中的字符串。

构建

以下文字直接读可能有点难以理解，建议配合画 SAM 工具理解。
如果你突然读不懂了或者感觉哪里不是很显然，不妨回去看看 $\mathrm{endpos}$ 和 $\mathrm{link}$ 的定义及性质。

SAM 的构建是在线的。

假设我们已经构建好了 $\mathrm{pre}(s, i - 1)$ 的 SAM，要构建 $\mathrm{pre}(s, i)$ 的 SAM。

不妨令 $c = s_i$。

显然添加进 $c$ 后会出现一个新的等价类，其中仅有 $\mathrm{pre}(s, i)$，设其为 $u$，设 $\mathrm{pre}(s, i -1)$ 所在的状态为 $last$，显然有 $\mathrm{len}(u) = \mathrm{len}(last) + 1$。

考虑添加进 $c$ 后哪些状态会受到影响，发现只可能是原串（$\mathrm{pre}(s, i - 1)$）的后缀所在的等价类。我们可以通过从 $last$ 所在的状态跳 $\mathrm{link}$ 得到。

设我们当前跳到的状态为 $p$，我们讨论一下 $\delta(p, c)$ 的情况。

若 $\delta(p, c) = \mathrm{null}$，则说明之前没有出现过这些串，那么 $p$ 本身不受到影响，根据转移的定义，有 $\delta(p, c) = u$。
若一直往上跳直到跳到根都满足 $\delta(p, c) = \mathrm{null}$，说明此时 $\mathrm{pre}(s, i)$ 的所有后缀都在等价类 $u$ 中，故有 $\mathrm{link}(u) = start$。

否则，我们设 $q = \delta(p, c)$，若有 $\mathrm{len}(q) = \mathrm{len}(p) + 1$，则说明 $q$ 的代表元就是 $p$ 的代表元后面加上 $c$。$q$ 本身不受到影响，且根据 $\mathrm{link}$ 的定义，有 $\mathrm{link}(u) = q$。
若存在这种情况，我们发现 $u$ 不会对后面其他串产生影响，所以此时已经完成了对 $\mathrm{pre}(s, i)$ 的 SAM 的构建。

若 $\mathrm{len}(q) > \mathrm{len}(p) + 1$，我们发现以 $s_{i - \mathrm{len}(p), i}$，以及 $q$ 中其他比 $s_{i - \mathrm{len}(p), i}$ 短的字符串的 $\mathrm{endpos}$ 都添加了一个元素 $i$，而另一部分则没有变化。于是状态 $q$ 就被分裂开来了。我们不妨令 $\mathrm{endpos}$ 更新了的那部分被分裂出来，设其为 $v$。则：

• $\mathrm{len}(v) = \mathrm{len}(p) + 1$。
• 原先 $q$ 的所有转移也是现在分裂后的两个状态的转移，可以由定义得到。
• $\mathrm{link}(q) = v$，$\mathrm{link}(v)$ 则为原本 $q$ 的 $\mathrm{link}$，且 $\mathrm{link}(u) = v$。可以由 $\mathrm{link}$ 的定义得到。
• 对于所有指向原先 $q$ 的转移，代表元小于 $\mathrm{len}(v)$ 的转移指向 $v$，另一部分指向新的 $q$。

其他几个都很好处理，我们来考虑一下指向 $v$ 的转移。
我们发现被更新的转移的等价类一定在后缀连接树上是 $v$ 的祖先（由定义得到），于是只要从 $p$ 开始继续跳 $\mathrm{link}$，将所有指向 $q$ 的转移改成指向 $v$ 即可。
用与上面第二种情况类似的分析可以得到，若跳到的某个状态的 $c$ 的转移不是 $q$，则之后的状态的 $c$ 的转移也一定不是 $q$。

一些性质及证明

SAM 的状态数上限

SAM 的状态数上限为 $2n - 1$。
我们考虑构建 SAM 的过程，发现每次添加一个字符至多会多出两个状态。另外，不难发现添加前 $2$ 个字符时一定只会多出一个状态。加上初始状态，总状态数上限为 $1 + 1 + 1 + 2 \times (n - 2) = 2n - 1$。

SAM 的转移数上限

SAM 的转移数上限为 $3n - 4$。
我们考虑抠出任意一棵以初始状态为根的生成树。显然生成树上的边数上限为 $2n - 2$。
对于任意一个 $s$ 的后缀，我们记录其在 SAM 上转移时经过的第一条非树边。
考虑任意一条非树边 $(u, v)$，一定存在一条从初始状态到 $u$ 的只经过树边的路径，且一定存在一条从 $v$ 到接受状态的路径。
也就是说，任意一条非树边一定时某个后缀在 SAM 上转移时经过的第一条非树边。故非树边数量上限为后缀的数量。
显然一定有一种扣生成树的方式使得前两个后缀的转移不经过非树边。故转移数上限为 $2n - 2 + n - 2 = 3n - 4$。

构建 SAM 的时间复杂度

我们考虑构建 SAM 时的三种情况。
第二种情况的时间复杂度显然是 $O(\left|s\right|)$。
第一种情况可以视为在 SAM 中填加转移，故复杂度与转移数同为 $O(\left|s\right|)$。
第三种情况则可以视为遍历指向某个状态的转移，时间复杂度也是 $O(\left|s\right|)$。
故总时间复杂度为 $O(\left|s\right|)$。

注意实际应用中为了实现方便在第三种情况复制转移时一般会直接枚举所有 $\left|\Sigma\right|$ 种转移，这样时间复杂度会变成 $O(\left|s\right| \left|\Sigma\right|)$。

另外，对于字符集很大的情况，可以使用 map 来实现，时间复杂度变为 $O(\left|s\right| \log \left|\Sigma\right|)$

代码实现

struct SAM {
	int tot, lst;
	int len[2000005], link[2000005];
	int delta[2000005][26];

	SAM() {link[0] = -1;}
	void insert(char ch) {
		int c = ch - 'a', now = ++tot;
		len[now] = len[lst] + 1;
		for (int p = lst; p != -1; p = link[p])
			if (!delta[p][c]) delta[p][c] = tot;
			else if (len[delta[p][c]] == len[p] + 1) {link[now] = delta[p][c]; break;}
			else {
				int q = delta[p][c], v = ++tot;
				len[v] = len[p] + 1;
				memcpy(delta[v], delta[q], sizeof(delta[v]));
				link[v] = link[q], link[q] = v, link[now] = v;
				for (int i = p; delta[i][c] == q; i = link[i]) delta[i][c] = v;
				break;
			}
		lst = now;
		return ;
	}
} sam;

应用

求子串出现次数

相当于求其 $\mathrm{endpos}$ 的大小。
根据 $\mathrm{link}$ 的性质 2，只要在 $\mathrm{link}$ 树上 DP 即可。
另一种实现是，将所有状态按 $\mathrm{len}$ 排序后从大到小将其贡献加给父亲，本质上也是树形 DP。

例题：洛谷 P3804【模板】后缀自动机（SAM）。

求本质不同子串个数

答案为每个等价类的大小，即：

$$\sum\limits_u \mathrm{len}(u) - \mathrm{len}(\mathrm{link}(u))$$

同样的方法也能求本质不同子串长度之和，即：

$$\sum\limits_u \dfrac{\mathrm{len}(u) \times (\mathrm{len}(u) + 1)}{2} - \dfrac{\mathrm{len}(\mathrm{link}(u)) \times (\mathrm{len}(\mathrm{link}(u)) + 1)}{2}$$

例题：SDOI2016 生成魔咒。

求字典序第 k 小子串

等价于在给每条边按边权排序后的第 $k$ 小路径，拓扑排序求出每个状态的路径数即可。时间复杂度为 $O(ans \times \left|\Sigma\right|)$。

注意当 $k = 1$ 时，可以贪心走最小的边。
由此我们也可以得到求最小表示法的方法：将字符串复制一遍接在后面，然后在 SAM 上贪心走最小边。

例题：TJOI2015 弦论。

求子串第一次出现的位置

不妨设要求的是第一次出现的结尾所在的位置。

我们考虑构建 SAM 的过程。
每个状态的第一次出现的位置一定是在该状态被创建时确定的。
当创建 $\mathrm{pre}(s, i)$ 的状态时，其答案为 $i$。
当复制结点时，$v$ 的答案为 $q$ 的答案。

求子串的 endpos

我们加强一下 $\mathrm{link}$ 的性质 2。

我们发现某个串的每次出现都对应一个以它为后缀的 $s$ 的前缀的第一次出现，所以求一下每个串第一次出现的位置，然后在后缀链接树上 dfs 即可。

求最短未出现串

一个串没有出现等价于其在 SAM 上最终转移到 $\mathrm{null}$。要求最短，一定是最后一步转移到 $\mathrm{null}$。直接在 SAM 倒过来 DP 即可。

求两个串的最长公共子串

设这两个串分别为 $s$ 和 $t$。

我们对 $s$ 建立 SAM，然后用 $t$ 的每个前缀去匹配最长的后缀。

具体来说，假设当前在状态 $u$，匹配到了 $\mathrm{pre}(t, i)$，答案为 $l$。如果 $u$ 有 $t _ {i + 1}$ 的转移，则直接转移，并且 $l \gets l + 1$。

否则，我们就要缩小当前匹配的串。我们发现状态 $u$ 内的所有串都不可能成为答案，所以直接 $u \gets \mathrm{link}(u)$，直到 $u = start$ 或 $\delta(u, t _ {i + 1}) \neq \mathrm{null}$。

每次操作至多使 $l$ 增加 $1$，所以是线性的。

求多个串的最长公共子串

对于最短的串建 SAM，然后用其他串在上面跑两个串的算法，每次跑完对于每个状态取个历史最小值，然后再用后缀链接树上的儿子更新答案，即如果儿子有值则将该状态的答案设为 $\mathrm{len}$。

例题：SPOJ LCS2 - Longest Common Substring II。