后缀数组
后缀数组可以解决有关后缀的问题废话。那么暴力做法肯定是把每个后缀全部取出来，然后按照字典序排序，但是这样复杂度是 \(\Theta(n^2\log n)\) 的。
后缀数组可以解决以下问题：
- 最长重复子串
- 多个串的最长公共子串
- 不同子串个数
算法详解
面对这些问题，我们需要 \(3\) 个数组：\(sa\), \(rank\), \(height\) 数组。
\(sa_i\) 表示排名为 \(i\) 的后缀，在原串的位置。
\(rank_i\) 表示后缀 \(i\) 的排名
\(height_i\) 表示后缀排名为 \(i\) 的后置和后缀排名为 \(i-1\) 的后缀的最长公共前缀。
https://zhuanlan.zhihu.com/p/561024497
标签：子串,后缀,rank,height,数组,half,排名 From： https://www.cnblogs.com/legendcn/p/18333507