对于一个字符串(S)，我们记后缀 (Suf_i) 为从 (i) 开始一直到末尾所形成的子串（(S_iS_{i+1}...S_{len})）。
现在我们要对所有后缀按照字典序排序。记 (sa_i) 表示排名第 (i) 的后缀的起始位置，(x[i]) 表示 (Suf_i) 的排名。
考虑使用一种倍增的方法排序：一开始我们提取每个后缀的长度为 (1) 的字符进行排序；然后将每个后缀的第 (1) 个字符作为第一关键字，第 (2) 个字符作为第二关键字，对这些长度为 (2) 的字符串进行排序；然后将每个后缀的前 (2) 个字符作为第一关键字，第 (3) 和第 (4) 个字符作为第二关键字，将长度为 (4) 的字符串进行排序……
由于我们对每个后缀长度为 (2n) 的字符串排序时，长度为 (n) 的字符串的排名已经确定，所以这个算法的正确性是显然的。
如果用 (sort) 直接排序，加上倍增的一个 (log) 总复杂度是 (O(nlog^2n)) 的，考虑优化：由于只有两个关键字且值域范围较小，我们可以使用基数排序，一种 $O(n) $ 的排序方式。这个不太好讲解，最好靠自己理解，实在看不懂可以背。代码中 (y) 数组的含义是第二关键字排名第 (i) 的第一关键字的位置为 (y_i) （这好像是唯一能提供的帮助了）。
好了现在通过慢慢理解你现在求出了 (sa) 数组和 (x) 数组了，我们现在用他们来搞点事情（毕竟不可能让你排个序就完了）。
记 (lcp(i,j)) 为 (Suf_i) 和 (Suf_j) 的最长公共前缀，(height_i) 表示 (lcp(sa_i,sa_{i-1}))。
假设我们现在已经拥有了 (height) 数组，考虑如何快速求 (lcp) ：容易发现（假设(x_j>x_i)）
比较通俗的理解就是一个排名为 (i) 的字符串，相对于与排名为 (j(j>i+1)) 的串的 (lcp) 来说，与排名为 (i+1) 的串的 (lcp) 肯定不会更短。
有了这个性质以后,我们发现求两个后缀的 (lcp) 就相当于求一个区间最小值,一个 (ST) 表就可以解决.
好了现在看怎么求 (height) 数组:
设 (h_i=height_{x[i]}),人话的意思就是 (h_i) 表示 (Suf_i) 与它排名前一位的后缀的 (lcp) 。
可以发现一个关系：
我们首先发现 (Suf_i) 与 (Suf_{sa[x[i-1]-1]+1 }) 的 (lcp) 一定为 (h_{i-1}-1)（前提是 (h_{i-1} eq 0)），因为 (h_igeq h_{i-1}-1) 这种关系我们可以直接 (O(n)) 推出 (h) 数组，在还原一下就能回到 (height) 数组了（(height_i=h_{sa[i]})）。
- 例题：