#P5668. 后缀排序

    ID: 4669 传统题 1000ms 256MiB 尝试: 64 已通过: 15 难度: 5 上传者: 标签>CF1800普及+/提高-后缀数组倍增基数排序计数排序

后缀排序

题目描述

这是一道模板题。

读入一个长度为 n n 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 1 到 n n 。

输入格式

一行一个长度为 n n 的仅包含大小写英文字母或数字的字符串。

输出格式

一共 nn 个整数,每行一个整数,第 i i 个整数为 SA[i] \text{SA}[i]。

ababa
5
3
1
4
2
mississippi
11
8
5
2
1
10
9
7
4
6
3

数据范围与提示

1≤n≤105 1 \leq n \leq 10 ^ 5

相关

在下列比赛中:

hash