Problems
Suffix array
Suffix array
Given a string. Build the suffix array for this string. The suffix array is a lexicographically sorted array of all string suffixes. Each suffix is given by an integer - the starting position.
String s is lexicographically less than the string t, if there exists such i that si
< ti
and sj
= tj
for all j < i. Or if such i does not exist and the string s is shorter than string t.
Here si
is the code of i-th symbol of string s.
Input
One line that represents the English literary text. The length of the text is no more than 105
. The codes of all symbols in the text range from 32 to 127.
Output
Print n numbers - the suffix array of a given string.
Input example #1
99 bottles of beer.
Output example #1
14 3 11 19 2 1 15 4 16 17 9 13 8 12 5 18 10 7 6