【模板】后缀排序
考虑首先将所有长度为 \(1\) 的子串进行排序，然后将所有长度为 \(2\) 的子串排序，长度不足的以空字符补齐。以此类推，每次排序的子串长度均是上一次排序的子串长度的两倍。最后一次排序后，所有子串均已排序完毕，此时得到的序列即为后缀数组。
考虑如何快速进行排序，若我们已经完成对于长度为 \(2^k\) 的子串的排序，那么我们可以利用这个结果对长度为 \(2^{k+1}\) 的子串进行排序。我们可以将长度为 \(2^{k+1}\) 的子串看作长度为 \(2^k\) 的两个子串的组合，那么我们只需要对这两个子串的排序结果进行归并即可得到长度为 \(2^{k+1}\) 的子串的排序结果。
发现归并的实质是以前半部分和后半部分的排名分别为第一关键字和第二关键字进行排序，使用基数排序即可优化至 \(O(n)\)。
同时由于我们得到了排名数组的逆数组，我们可以利用这个逆数组快速完成第二关键字的排序，进而优化常数。
[JSOI2007] 字符加密
将字符串 \(S\) 复制一次后得到字符串 \(SS\)，求出其后缀数组后按排名枚举所有长度大于等于 \(\left\lvert S \right\rvert\) 的后缀添加进答案中即可。
[USACO07DEC] Best Cow Line G / [USACO07NOV] Best Cow Line S
考虑如何暴力求解，对于当前的情况比较当前剩余的字符串的前缀和后缀的字典序大小关系并选择较小的那个即可，复杂度为 \(O(n^2)\)。
考虑如何优化，发现我们其实是需要求出字符串中所有前缀和后缀的字典序大小关系，将字符串反转后拼接到原字符串后，我们可以直接求出所有前缀和后缀的字典序大小关系，这样就可以将复杂度优化至 \(O(n \log n)\)。
不同子串个数
考虑将所有后缀排序后枚举并考虑其贡献，发现其贡献为当前后缀长度减去与前一个后缀的最长公共前缀长度，因此我们可以利用后缀数组求出 \(\operatorname{height}\) 数组后求和即可。
[SDOI2008] Sandy 的卡片
考虑通过二分答案转化为判定问题。
将所有的字符串差分后拼接起来，然后求出其后缀数组。进而只需要判定是否存在长度为 \(k\) 的子串使得其在每个字符串中均出现，判定 \(\operatorname{height}\) 序列上是否存在一个区间满足其最小值大于等于 \(k\) 且出现了所有的字符串即可。
[SCOI2012] 喵星球上的点名
首先将所有的字符串拼接起来并求出后缀数组，并通过后缀数组对于每个询问串确定出其在后缀数组中出现的区间。
现在问题转化为了求出区间内的颜色种类数和颜色出现次数，其中第一问可以通过莫队算法解决，考虑如何求解第二问。
我们可以将其贡献在时间序上差分，进而只需要求出每个时间点的贡献即可。我们可以发现，对于每个时间点，若某个颜色不再出现在莫队区间中，那么其产生剩余操作数的负贡献，若某个颜色在莫队区间中首次出现，那么其产生剩余操作数的正贡献。在莫队的过程中求解即可。
[HEOI2016/TJOI2016] 字符串
首先通过二分答案转化为判定问题。
接下来我们的问题转化为：
给定一个常数 \(k\)，判定后缀 \(a\) 到后缀 \(b - k + 1\) 中是否存在一个后缀使得其与后缀 \(c\) 的最长公共前缀长度大于等于 \(k\)。
我们可以发现，与后缀 \(c\) 的最长公共前缀长度大于等于 \(k\) 的后缀在后缀数组上一定是连续的，因此我们可以通过二分求出其具体范围。
下面我们只需要判定是否存在一个 \(i \in \left[a, b - k + 1\right]\)，满足其后缀数组的值在上文求出的范围内即可，此问题为二维数点问题，使用主席树求解即可。
总复杂度 \(O(n \log^2 n)\)。
[AHOI2013] 差异
对于算式的前半部分可以化简为常数，对于后半部分可以转化为 \(\operatorname{height}\) 数组上的所有区间的最小值之和，使用单调栈维护即可。