构造后缀数组
我们会得到两个数组 $sa_i$ 表示排名为 $i$ 的后缀是哪一个，$rk_i$ 表示后缀 $i$ 的排名。
这里只讲倍增做法。
原理非常简单，如下图：
实现需要一个对两位关键字进行排序的基数排序，设 $y_i$ 表示按照第二维关键字排序，排名为 $i$ 的是哪一个位置。设 $rk_i$ 表示第 $i$ 个位置，第一维关键字排序，排名是多少。
我们按照 $i$ 从小到大把 $rk_{y_i}$ 加入我们的桶中（我们用桶排来实现），对桶做前缀和之后，从大到小枚举 $n$，按照 $rk_{y_i}$ 来重新计算每个位置的排名。
这样做正确性显然，考虑如果两个位置第二维关键字排名不同，而第一维相同，那么排名越大的会先被枚举到，导致排名变大。如果第一维就不同，那么第一维更优的显然会排名更小。
所以就可以简单构造了，具体代码请到代码仓库。
求 height
LCP 的定义是最长公共前缀，以下用 $LCP(i,j)$ 表示编号为 $i$ 的后缀和编号为 $j$ 的后缀的 LCP，我们令 $Height_i=LCP(sa_i,sa_{i-1})$，而 $Height_1$ 可以视作 $0$。我们考虑如何求 $Height$ 数组。
- 引理：$Height_{rk_i}\ge Height_{rk_{i-1}}-1$。
证明：如果 $Height_{rk_{i-1}-1}$ 小于等于 $1$，那么上面这个式子显然成立，这是因为 $Height_i\ge 0$。
如果 $Height_{rk_{i-1}-1}>1$，我们考虑设后缀 $i-1$ 为 $aAD$，那么后缀 $i$ 就是 $AD$，其中 $A$ 是一个长度为 $Height_{rk_{i-1}}-1$ 的字符串，由于 $Height$ 数组的定义，我们考虑后缀 $sa_{rk_{i-1}-1}$ 这个字符串一定是 $aAB$ 的形式，所以 $sa_{rk_{i-1}-1}+1$ 这个后缀一定是 $AB$ 的形式，所以这个后缀一定排在后缀 $i$ 的前面，所以我们可以知道 $Height_{rk_i-1}$ 一定包含字符串 $A$，所以结论成立。
我们利用上面这个东西就可以 $O(n)$ 的来求 $Height$ 数组了。
有一个结论是 $LCP(sa_i,sa_j)=\min_{i+1\le k\le j}Height_k$，这个可以感性理解一下，如果 $Height$ 一直大于某个值，那么这一段就一直有，反之，肯定是在一个后缀中改变。