D. 后缀数组

    传统题 4000ms 256MiB

后缀数组

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

字符串下标为 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

题意整理;原题与输入输出格式对照。

望京周六班级训练赛

未参加
状态
已结束
规则
XCPC
题目
4
开始于
2026-10-17 9:35
结束于
2026-10-17 11:35
持续时间
2 小时
主持人
参赛人数
11