D - Suffix Concat
Editorial
/
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
長さ N の文字列 S が与えられます。各 i (1≦i≦N) について、S の i 文字目から N 文字目までの部分文字列を S_i と呼ぶことにします。
S_1,S_2,...,S_N を好きな順番で連結して得られる文字列のうち、辞書順で最小のものを求めてください。
制約
- 1≦N≦10^5
- S の長さは N である。
- S は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N 行出力せよ。i 行目には p_i を出力せよ。
ただし、(p_1,p_2,...,p_N) は、1 から N までの順列であって、次の条件を満たすものである。
- S_{p_1},S_{p_2},...,S_{p_N} をこの順番で連結して得られる文字列が、辞書順で最小である。
(p_1,p_2,...,p_N) が複数通りある場合、どれを出力してもよい。
入力例1
3 arc
出力例1
1 3 2
arc
,c
,rc
の順番で連結して得られる arccrc
が、辞書順で最小です。
入力例2
2 zz
出力例2
1 2
他には、2,1 の順番で出力してもよいです。
入力例3
5 abaab
出力例3
3 1 4 2 5