后缀数组
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
字符串下标为 0 到 n−1。将所有后缀按字典序排序,求排序后的起点数组 SA,以及每个后缀与排序中前一个后缀的最长公共前缀长度数组 Height。
输入格式
一个长度不超过300000的字符串。
输出格式
第一行输出 SA 的 n 个下标;第二行输出 Height 的 n 个值,其中第一项为0。
样例输入
ponoiiipoi
样例输出
9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2
题意整理;原题与输入输出格式对照。