后缀数组由字符串的所有后缀排序后得来，可以高效地处理一些字符串问题。
构造后缀数组的朴素算法是$\mathcal{O}\left(n^2\log_2 n\right)$的，虽然排序只要$\mathcal{O}\left(n\log_2 n\right)$的时间，但字符串比较却需要线性时间。
利用后缀的性质可以得到更快的算法，常用的有DC3算法（$\mathcal{O}\left(n\right)$）和倍增算法（$\mathcal{O}\left(n\log_2 n\right)$）。这里只讨论简单一些的倍增算法。
首先考虑怎样保存排序后的后缀，直接保存字符串显然不行，应该对所有后缀编号，后缀i表示由原串下标为i的字符开始的后缀，这样就可以直接保存后缀的编号。这里假设字符串下标从0开始。
倍增的思路是每次仅考虑每个后缀的前k×2个字符（$k\in\left\{2^x|x\in\mathbb{N}\right\}$），后缀$i$的排名可以由上一次排序时后缀$i$和后缀$i+k$的排名得到。
这样一直重复$\mathcal{O}\left(\log_2 n\right)$即可。
这样做的复杂度是$\mathcal{O}\left(n\log_2^2 n\right)$。因为字符集最大不超过$n$（超过了可以离散），所以可以使用计数排序，时间复杂度优化到$\mathcal{O}\left(n\log_2 n\right)$。
下面给出求后缀数组的代码。
计算出后缀数组后，最显然的一个应用就是进行字符串匹配，直接在后缀数组中二分即可。
但其实光是有后缀数组能解决的问题并不多，还需要两个辅助数组：$rank$和$height$。
$rank_i$表示后缀$i$在后缀数组的排名。
$height_i$表示后缀$i$和后缀$sa_{rank_i-1}$的最长公共前缀（LCP）长度，或者说$height_{sa_i}$表示后缀$sa_i$和后缀$sa_{i-1}$的LCP长度。
前者很好求，但求后者的朴素算法是$\mathcal{O}\left(n^2\right)$的，比求后缀数组的算法还慢。
快速求$height$数组的算法要利用一个性质：$height_i\geq height_{i-1}-1$
简单证明：设后缀$k$是排在后缀$i-1$前一位的后缀，它们的LCP长度显然是$height_{i-1}$。后缀$k+1$显然排在后缀$i$前面，而且$height_i$相对于$height_{i-1}$就是同时去掉了第一位，所以$height_i$至少是$height_{i-1}-1$。
求两个辅助数组的代码。
注意后缀数组有一个非常好的性质：对于$i<j<k$，后缀$sa_i$和后缀$sa_k$的LCP长度小于等于后缀$sa_j$和后缀$sa_k$的LCP长度，所以往往可以只考虑相邻元素的LCP，即$height$数组来解题。
http://poj.org/problem?id=2774 代码
求两个字符串的最长公共子串。
用一个在两个字符串中都不会出现的字符把它们连接起来。
答案一定是在$height$数组中的最大元素，不过要略去那些对应的两个后缀在相同的给出串中的元素。
http://poj.org/problem?id=3261 代码
求一个序列中重复至少$k$次的最长子段。
这次是数字串了，但还是可以用老办法求后缀数组。
二分答案，在$height$数组中去掉小于答案的元素，这样会把它分成若干组，每一组都是在数组中连续的一段大于等于答案的元素，如果最大的那组的元素个数不小于$k$，就可行。
证明就不给出了，因为我不会证。。。
对$height$数组分组也是用后缀数组解题时很常用的方法。
另外这题也可以用哈希做，代码量要小很多。代码
评论 (0)
