← 返回题目列表

AtCoder · nikkei2019ex_a

A. 前缀数组

中文机器翻译题面 查看原题

配点 : 200 点

問題文

文字列 S 。 对于S 可以得到第 前缀数组 查找 。

但是,前缀数组是后缀数组 (链接位于维基百科“后缀数组”),定义中的“后缀”更改为“前缀”。

(具体示例参见下面的输入/输出示例1。)

制約

  • 1 ≦ |S| ≦ 100,000
  • S 仅由小写字母组成。

入力

输入是按以下格式从标准输入给出的。

S

出力

S 的前缀数组 如果我们按字典顺序对 |S| 行输出。


入力例 1

chokudai

出力例 1

1
2
3
4
5
6
7
8

chokudai 的所有后缀进行排序,我们得到:

  • c
  • ch
  • cho
  • chok
  • choku
  • chokud
  • chokuda
  • chokudai