#111. 后缀排序

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

这是一道模板题。

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

输入格式

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

输出格式

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

样例

样例输入

ababa

样例输出

5 3 1 4 2

数据范围与提示

1n1061 \leq n \leq 10 ^ 6