后缀数组与后缀自动机
后缀数组
基础模板
后缀数组 $sa[i]$：将一个字符串的每个后缀排序后第 $i$ 小的后缀的编号。
辅助数组 $rank[i]$：后缀 $i$ 的排名
对于一个字符串，我们可以在 $O(n\log n)$ 的时间里得到其后缀数组。主要思想是倍增与基数排序。模板如下：
1 | struct node{ |
基于后缀数组，我们可以得到一个非常有用的的东西：Height 数组。
$Height[i]$：排名为 $i$ 的后缀与排名为 $i-1$ 的后缀的最长公共前缀。
容易知道，$Height[rank[i]]\ge Height[rank[i-1]]-1$。
根据这一定理，我们可以线性地求出 Height 数组。
代码如下：
1 | for(int i=1,k=0;i<=n;i++){ |
Height 数组的灵活运用
以上内容都是非常基础、模板化的，后缀数组的核心在于灵活地运用 Height 数组，从而解决各种与子串相关的问题。
这其中最重要的定理就是：两个后缀 $l,r$ 的最长公共前缀等于 $\min\limits_{i=rank[l]+1}^{rank[j]} Height_i$。
有了这个定理，我们只要预处理出 ST 表，就可以 $O(1)$ 的查询两个后缀的 LCP 了！（顺便提一句，用哈希+二分可以在 $O(log n)$ 的时间内达成同样的目的）。
与之相关的有若干经典问题，包括不同子串的数目，出现至少 k 次的子串的最大长度，连续的若干个相同子串等等，因为较为简单，可以在OI-Wiki上自行查阅，不再赘述。
这部分的例题有：NOI2016优秀的拆分，NOI2015品酒大会，AHOI2013差异等。
通过这些题目，我们可以总结出后缀数组求解子串问题的主要思路：
- 构建出后缀数组，得到 Height 数组；
- 根据后缀数组的性质，按照某种顺序统计相邻元素的贡献进行求解：
- 按照排序的顺序，利用 ST 表求解。这一方法多用于统计与长度相关的多个子串问题。
- 按照 Height 数组的顺序，利用并查集求解。这一方法多用于统计与长度相关的两个子串问题。
当然，很多题目在已经求出 Height 数组之后会变成其他经典问题，要注意识别。
几个相关的小练习
SDOI2016 生成魔咒
题意：每次增加一个字符，求当前字符串的本质不同子串个数。
考虑在末尾加字符对后缀改变太大，我们将串翻转。变成在开头加字符后，我们要统计当前字符开头的与之前不同的子串个数。我们每次把已经统计的串扔进 set，则只用统计与当前的排名相邻的串的贡献（相邻两个一定是重复的最多的）。则每次的答案是之前的答案加上当前的子串总数减去与排名前后的重复子串个数加上排名前后的贡献（之前减掉了，现在加回来）。
TJOI2019 甲苯先生和大中锋的字符串
题意：将字符串中恰好出现 $k$ 次的子串按照长度分类，求数量最多的那类的长度（相同取最大）。
我们按后缀顺序枚举每个后缀，看这个后缀的哪些前缀可能构成贡献。对于后缀 $[i,i+k-1]$，他们可能构成贡献的上界应该是这个区间内 Height 数组的最小值。下界呢？为了确保子串只在这几个后缀的前缀中出现，我们需要让子串的长度大于 $\max(height_i,height_k)+1$。如果不满足的话那么 $i-1$ 或者 $k$ 开头的前缀也会出现，就不合法了。找到上下界后利用差分计算答案即可。
更加深入地理解后缀数组
给定一个字符串，构建其后缀数组是很容易的。那么我们如何根据一个排列构建一个后缀数组是该排列的字符串呢？
对于后缀数组中两个相邻的元素，显然有 $str_{p_i}\le str_{p_{i+1}}$。什么时候不能取等呢？不难发现，这与 $p_i+1$ 和 $p_{i+1}+1$ 的位置关系有个。若 $p_i+1$ 在 $p_{i+1}+1$ 的后面，则 $str_{p_i}< str_{p_{i+1}}$ 一定成立；否则可以取等。
因此，所有的字符按照后缀的顺序一定会构成一条不等式链，形如 $str_{p_1}\otimes str_{p_2}\otimes str_{p_3}\otimes…\otimes str_{p_n}$，其中 $\otimes\in \left{<,\le\right}$。 这样，如果要构造任意一个原串是很容易的，如果要构造一个字符集最小的原串也是可以贪心做到的。
有了上面的基础，我们看一看这道题：
CTSC2016 萨菲克斯·阿瑞
题意：求由 $m$ 种字符组成，其中第 $i$ 种字符出现次数不超过 $c_i$，且长度为 $n$ 的字符串，共有多少种不同的后缀数组。
声明：以下内容参考自 NOI 捧杯爷虞皓翔的题解，膜拜%%%
对于上面的每一条链，我们称其有 $k$ 段当它由恰好 $k-1$ 个小于号连接。既然要统计字符集为 $m$ 的后缀数组数量，我们不妨先求出有 $m$ 段的后缀数组个数。
观察 $m=3$ 的情况。设有 $A$ 个备选的 $a$，$B$ 个备选的 $b$，$C$ 个备选的 $c$，则根据多重组合数（可重排列），我们知道小于等于 $3$ 段的后缀数组有 $\begin{pmatrix} A+B+C \ A,B,C \end{pmatrix}$ 个。但我们要减掉小于等于 $2$ 的那些，不难发现，这是一个容斥的过程。也就是说，最后的答案应该是：
$$
\begin{pmatrix}
A+B+C \
A,B,C
\end{pmatrix}
\begin{pmatrix}
A+B+C \
A+B,C
\end{pmatrix}
\begin{pmatrix}
A+B+C \
A,B+C
\end{pmatrix}
+
\begin{pmatrix}
A+B+C \
A+B+C
\end{pmatrix}
$$
对于更大的情况，只需要推广这个容斥即可。
但是等等，我们要求的是字符集为 $m$ 的答案！我们知道，每个排列有唯一的段数。因此我们只需要在统计该段数的时候把这个排列统计进去即可。
还有一个小问题，即完全贪心填出来的字符串可能不符合出现次数 $c_i$ 的限制。不过没关系，我们直接把后面的字符当做当前字符来填即可。只有确保当前字符是用完了的就是正确的！
最后的问题在于如何计算上面那个容斥。我们可以采用一个简单的 DP 来求得容斥系数。定义状态 $f_{i,j,k}$ 表示用了 $i$ 个字符填完 $j$ 个位置，且最后一个段用了 $k$ 个字符的答案。DP的转移不难，也超出了后缀数组的范畴，故不展开阐述。请参见上面的链接。
后缀数组与区间操作
在 Height 数组的部分，我们了解到，对于排序后的数组，我们很多时候只用统计相邻两个元素的贡献，就能得到全局的贡献。其实，利用后缀数组，我们也可以快速对给定的若干子串排序，从而进行区间操作。
十二省联考2019 字符串问题
题意：给定一个字符串和两类子串，给出若干 $A$ 类串支配 $B$ 类串的支配关系，我们能把两个 $A$ 类串拼接当且仅当第一个 $A$ 类串支配的某个 $B$ 类串是第二个 $A$ 类串的前缀。每个串拼接的次数不限，求能拼接的最长串长或判断无限长。
首先抽象出问题：把所有的 $A,B$ 串看做点，有若干 $A\rightarrow B$ 的有向边，$B\rightarrow A$ 存在有向边当且仅当 $B$ 是 $A$ 的前缀，求最长路。
如果直接枚举每对 $A,B$，时空复杂度都是平方级，显然不能通过。这时考虑先将原串进行后缀排序。利用排序的后缀，我们可以快速对 $A$ 串也进行排序（若两个串左端点的 LCP 大于任意串长，比较串长；否则按左端点的后缀序）。这时，我们发现，每个 $B$ 串所能连边的 $A$ 串一定是排完序后一段连续的区间。考虑用数据结构优化。
将排序后的 $A$ 串建一棵线段树，父亲向儿子连边。这样以后 $B$ 串只用像区间修改的方式去连刚好包含的点即可。还剩一个问题：边权怎么办？因为只有 $A$ 串的长度对答案有贡献，所以我们可以将每个 $A$ 串拆成入点和出点，这两个点之间的边权就是 $A$ 串的长度，其他边赋值为 $0$ 即可。
建完边后只需要用 Tarjan 判一下有没有环，再在 DAG 上进行 DP 即可。
多个字符串的拼接&结合主席树
对于多个字符串的子串相关问题，有时需要将多个字符串拼接到一起求后缀数组。这时我们可以根据需要在两个字符串之间插入一个字典序最小/最大的字符，以起到分隔的作用。而这种多个字符串的问题有时也会涉及只在某一区间内的字符串的统计。这样我们就会有两组限制：ID 的 $[l,r]$ 和 SA 的 $[L,R]$。这时我们既可以转化成二维数点问题，用树状数组完成，也可以用值域主席树来做。
CF1037H
题意：给出一个字符串，有若干询问，每次给出 $l,r$ 和另一个字符串，找出原字符串在 $l,r$ 中的子串中字典序大于给出字符串的字典序最小的子串。
为了将子串问题转化成后缀问题，我们枚举找到字符串与给出字符串的 LCP。由于字典序要严格大于，我们再枚举找到子串的下一个字符。问题转化为在原串的后缀中找到与某个串完全相同的前缀。后缀排序后显然答案在一个连续的区间内。但如何判断答案是否在 $l,r$ 的限制内呢？这时就需要用到主席树。在主席树中插入每个后缀的排名，然后查询就很简单了。
注意到每次的区间是严格包含下一层的区间的，因此我们可以用倍增或二分快速地找到新的区间。
课后练习
CF452E，与品酒大会方法类似
CF204E，简单数据结构维护
CF873F，Height 数组的运用
NOI2018你的名字，二分+结合主席树
TJOI/HEOI2016字符串，二分+结合主席树
后缀自动机
基础模板
自动机的每个节点对于一个状态，需要存储：$fa,nxt[字符集],len$。
插入过程即从上一个节点找到一个合适的位置插入。具体有三种情况，建议理解性默写代码：
1 | struct node{ |
不难发现，如果将每个点与父亲连边，将会构成一棵树，称为 Parent Tree。这棵树与原 SAM 有如下关系：每个节点的终点集合等于其 子树 内所有终点节点对应的终点的集合。而每个状态对应的子串数量为 $len_i-len_{fa_i}$。
SAM与parent tree的灵活运用
因为 SAM 构成一张 DAG，所以很多统计问题可以转化为 DAG 上的 DP 来完成。如：
不同子串个数
令 $f_i$ 表示 $i$ 这个节点开始的字符串数量，则 $f_i=1+\sum\limits_{j\in nxt_i}f_j$，拓扑排序即可。当然也可以用上面的结论直接把每个节点的子串数量加起来。
不同子串的总长度
与上面的 DP 十分类似。
字典序第 $k$ 大子串
先用上面的方法处理出每个点开始的字符串数量，再模仿依次枚举字符求解。
注意：有些时候 DP 要放在 Parent Tree 上而非 SAM 上，这时统计的东西是相同子串的相关答案（如出现次数）。例如上面的问题，统计本质不同子串与位置不同子串需要区分开来。
两个字符串的最长公共子串
对第一个串建立后缀自动机，第二个串如果可以匹配就顺着匹配，否则暴力跳 $fa$。感觉和 AC 自动机的某些操作类似。
SAM的区间操作：线段树合并
有时我们希望多次询问与原串的某个子串相关的信息，这时需要用到线段树合并。我们在 SAM 的每个节点上存一棵动态开点权值线段树，值域为 $[1,n]$ 表示是否存在长度为该区间的以当前节点结尾的子串。一开始只有插入节点时在当前长度赋值。然后我们 DFS Parent Tree，每次将儿子的信息合并到父亲上。这样查询就变成了线段树上是否有某个区间的值。还是以前面用过的一道题为例：
CF1037H
题意：给出一个字符串，有若干询问，每次给出 $l,r$ 和另一个字符串，找出原字符串在 $l,r$ 中的子串中字典序大于给出字符串的字典序最小的子串。
首先套路地建好 SAM 并完成线段树合并操作，然后以递归地形式判断是否合法。向下递归时移动自动机的节点，每次枚举新字符判断是否有在查询区间的子串。
上述做法无论是思维难度还是代码难度都远小于后缀数组的做法。
NOI2018 你的名字
题意：给定一个模式串，每次询问给出文本串，求文本串有多少本质不同子串在模式串中没有出现过。
首先套路地建好 SAM 并完成线段树合并操作，然后考虑贡献。我们枚举文本串的每个节点作为终止节点，尝试找出在模式串中出现过的最长后缀。这可以利用前一次的答案，如果不合法则减小长度，如果长度与父亲相同就往父亲跳来解决。注意一个问题：这个终止节点的限制是作用于以其结尾的所有节点的，因此标记要打在序列上。