by Duck.
后缀数组
后缀数组（Suffix Array，SA）可以在 \(\mathcal{O}(n \log n)\) 的复杂度内对 \(S\) 的每个后缀进行字典序排序。
记后缀 \(i\) 表示后缀 \(S[i,n]\)。
SA 的核心在于得到两个数组 \(sa,rk\)。\(sa_i\) 表示字典序排名为 \(i\) 的后缀位置，\(rk_i\) 表示后缀 \(i\) 的字典序排名。容易发现这两个数组是互为逆运算的，也就是 \(sa(rk_i)=rk(sa_i)=i\)。
朴素的后缀排序，每次对两个串比较字典序需要 \(\mathcal{O}(n)\) 的复杂度，总复杂度 \(\mathcal{O}(n^2 \log n)\)。
SA 运用了倍增的思想，每次对等长的串进行字典序排序。对于长度不相同的，我们在末尾添加很小的字符保证其字典序更小。对于等长的字符串，我们可以将其切成两半，对于前后两端分别比较字典序。这件事为倍增比较的正确性提供了保证。
一个更重要的东西是 height 数组，绝大多数的 SA 题目都依赖于此。
定义 \(h_i=\operatorname{lcp}(sa_i,sa_{i-1})\)，也就是排名相邻的两个后缀的 \(\text{lcp}\)。不妨认为 \(h_1=0\)。
关于 \(h_i\) 最重要的一个性质：\(h(rk_i) \geq h(rk_{i-1})-1\)。这个性质可以帮助我们快速递推 height 数组。
height 数组的一些经典应用：
- 求后缀 \(i,j\) 的最长公共前缀：\(\operatorname{lcp}(i,j)=\min_{k=rk_i+1}^{rk_j}\{h_k\}\)。简要的解释为，对于排名在 \([rk_i,rk_j]\) 之间的所有后缀，他们的前 \(\operatorname{lcp}(i,j)\) 个字符必然都是相等的，从而答案就是 \([rk_i+1,rk_j]\) 的区间 \(\min\)。
- 本质不同子串数量：\(\dfrac{n(n+1)}{2}-\sum h_i\)。简要的解释为，重复的子串一定来源于排名相邻的后缀的 LCP。
P3809 【模板】后缀排序
在这里详细说一下 SA 的求解过程。
设 \(^wrk\) 表示长度为 \(w\) 的子串比较得到的 \(rk\) 数组，以 \(^{w/2}rk_i\) 和 \(^{w/2}rk_{i+w/2}\) 作为二元组的第一二关键字排序，就可以得到长度为 \(w\) 的子串的排序结果 \(^wsa\) 和 \(^wrk\)。二元组排序用基数排序即可。
当 \(w\geq n\) 时就可以得到每个后缀的排序结果。实现细节可以直接背板子。
时间复杂度 \(\mathcal{O}(n \log n)\)。
P4051 [JSOI2007] 字符加密
我们把原串复制一遍接在后面，那么所有循环同构都会作为一个子串出现。
根据 SA 比较字典序的原则，「把字符串切成前一半和后一半分别比较」是正确的，所以我们对整个串进行后缀排序，比较的依据只有这些循环同构。从而就实现了对所有循环同构字典序排序的效果。
时间复杂度 \(\mathcal{O}(n \log n)\)。
P4248 [AHOI2013] 差异
\(|T_i|+|T_j|\) 是定值，所有数对加起来会贡献 \((n-1)\times \dfrac{n(n+1)}{2}\)。只需要算后面的 LCP 部分。
考虑 height 数组，那么这个东西相当于求所有区间的最小值之和。用单调栈算一下作用区间即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
P7409 SvT
与上一题需要处理的问题是一样的，但是这里每次询问会给出一个点集。
考虑用虚树的思想减少状态，将给定的点 \(a_i\) 按照 \(rk\) 排序并离散化之后，求出每个点新的 \(h'_i=\operatorname{lcp}(sa(a_i),sa(a_{i-1}))\)，再用单调栈去处理。
先建出 SA 和 height 数组，用 ST 表预处理区间最小值即可每次 \(O(1)\) 回答 \(h'_i\)。
时间复杂度 \(\mathcal{O}(n \log n + \sum t \log t)\)。
CF1073G Yet Another LCP Problem
还是一样的问题，这回变成在两个集合里面选了。
于是我们简单容斥一下，分别计算只在 \(A\) 里选，只在 \(B\) 里选，以及在 \(A\cup B\) 里选的答案即可。
时间复杂度 \(\mathcal{O}(n \log n + \sum k\log k+\sum l\log l)\)。
P4070 [SDOI2016] 生成魔咒
这个东西要求我们动态维护 height，这当然是不可能的。
如果每次都要改变后缀，自然是困难的，那么我们考虑把串反过来，这样每次相当于插入一个新的后缀，并且不影响之前的所有后缀。
这件事情告诉我们，插入一个新的后缀只会影响与其排名相邻的后缀的 height。于是我们先把所有数离线下来反转建 SA，用 set 维护所有数的 height。插入新后缀，只需要减去其排名的前驱和后继的 LCP，再加上它和前驱以及它和后继的 LCP 即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
P3181 [HAOI2016] 找相同字符
一种神秘套路。
对于两个串的的问题，我们可以考虑将其拼接在一起，中间加一个分隔符，对这个大的串后缀排序。对于多个串，一样可以拼接，要在每两个串之间加上互不相同的分隔符。
对于这个题，我们考虑拼接，算所有相同的子串数量之和，这个东西就是后缀两两 LCP 之和。同时，我们还需要减掉只在 \(A\) 中出现的子串和只在 \(B\) 中出现的子串。于是我们建三个 SA，跑三次 height 数组，单调栈处理即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
SP1811 LCS - Longest Common Substring
考虑拼接在一起后缀排序，最长公共子串一定出现在排名相邻的后缀的 LCP 中。
按照排名从小到大枚举，判断两个后缀是否一个属于 \(A\) 一个属于 \(B\)，对 height 数组取最大值即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
SP1812 LCS2 - Longest Common Substring II
多个串的问题。
类似的问题还有：SP10570，P5546。