后缀数组是个很神奇的数据结构。
这是一道模板题。
概念
后缀数组处理的是一个字符串所有的后缀排序后的结果。
算法
我们考虑用倍增来解决这个问题。
第$H$轮排序的目标是让从所有位置开始$2^H$个字符的字符串都排好序
为了表述方便，我们定义一些数组。
在第$H$轮中：
$SA_i^H$表示排名为$i$的后缀从$SA_i^H$开始
$rnk_i^H$表示从i开始的后缀排名为$rnk_i^H$
然后考虑从第$H$轮转移到第$H+1$轮。
转移的时候先按照$rnk_{i+{2^H}}^H$排序，再按照$rnk_i^H$排序。
排序用基数排序，要不然复杂度多一个$log$。
初始情况注意一下即可。
基数排序
基数排序的核心是计数。
首先记录每一个数出现的次数，然后作次数的前缀和（算出每个数最后出现的位置），倒着循环把当前的数填入这个数可填的最后位置，并且把这个数可填的最后位置前移一格。