【模板】后缀排序：题解

思路

在原串末尾加入一个严格小于所有合法字符且只出现一次的哨兵。先按单个字符排序，并给相同字符赋相同类别编号。若已经知道每个位置开始的长度为 $2^k$ 的片段类别，则长度为 $2^{k+1}$ 的片段可以由“前一半类别、后一半类别”这个有序对唯一描述。

因此每轮按这两个类别组成的键排序并重新编号。当覆盖长度不小于带哨兵字符串长度时，所有循环移位的顺序已经确定。哨兵唯一且最小，删去哨兵位置后，其余循环移位顺序恰好就是原串全部非空后缀的字典序。

做法

上一轮的类别编号是从 $0$ 开始的连续整数。把已排序片段的起点统一向左移动 $2^k$，就得到按第二关键字有序的序列；再按第一关键字类别做稳定计数排序即可。这样每轮为线性复杂度。

正确性证明

初始轮按单字符 ASCII 值排序，所以类别正确表示长度为 $1$ 的片段。

假设第 $k$ 轮类别正确。长度为 $2^{k+1}$ 的片段由两个连续的长度为 $2^k$ 的片段组成，相对次序恰由两半类别组成的有序对决定。先按第二关键字有序，再按第一关键字稳定计数排序，得到有序对的字典序；按相邻有序对是否相同重新编号，就得到正确的新类别。由归纳法，每轮顺序和类别都正确。

最终覆盖长度不小于串长。若两个后缀在某个字符处首次不同，它们仍按该字符的 ASCII 值决定顺序；若一个后缀是另一个的前缀，较短后缀先遇到唯一最小哨兵，因而排在前面。这与题目要求的字典序完全一致。

复杂度分析

倍增轮数为 $O(\log n)$，每轮计数排序和重新编号均为 $O(n)$，总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

部分分算法

当 $n\le1000$ 时，可以枚举所有后缀起点，在比较器中逐字符比较两个后缀，最坏时间复杂度为 $O(n^2\log n)$。

当 $n\le100000$ 时，仍使用倍增排名，但每轮直接比较两个排名组成的二元组，时间复杂度为 $O(n\log^2 n)$，空间复杂度为 $O(n)$。