配点 : 200 点
問題文
文字列 S 。 对于S 可以得到第 前缀数组 查找 。
但是,前缀数组是后缀数组 (链接位于维基百科“后缀数组”),定义中的“后缀”更改为“前缀”。
(具体示例参见下面的输入/输出示例1。)
制約
- 1 ≦ |S| ≦ 100,000
- S 仅由小写字母组成。
入力
输入是按以下格式从标准输入给出的。
S
出力
S 的前缀数组 如果我们按字典顺序对 |S| 行输出。
入力例 1
chokudai
出力例 1
1 2 3 4 5 6 7 8
chokudai 的所有后缀进行排序,我们得到:
cchchochokchokuchokudchokudachokudai