A - Prefix Array

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

文字列 S が与えられます。SPrefix Array を求めなさい。

ただし、Prefix Arrayとは、Suffix Array (リンク先は Wikipedia「接尾辞配列」) の定義における「接尾辞」を「接頭辞」に変更したものです。

(具体例は下記の入出力例 1 で確認できます。)

制約

  • 1 ≦ |S| ≦ 100,000
  • S は小文字アルファベットのみからなる。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S の Prefix Array を |S| 行に出力せよ。


入力例 1

chokudai

出力例 1

1
2
3
4
5
6
7
8

chokudai のすべての接尾辞を辞書順にソートすると、以下のようになります。

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