10312: CF EDU - Suffix Array - Step 1 - A. Suffix Array - 1
[Creator : ]
Description
Now try to implement the algorithm that was discussed in the lecture.
Write a program that reads the string $s$ and prints the suffix array $p$ for it.
Write a program that reads the string $s$ and prints the suffix array $p$ for it.
Input
Input contains a single string $s$ of length $n\ (1≤n≤100,000)$. String consists of small english letters.
Output
Print $n+1$ distinct integers, indices of first characters of suffixes of $s$, ordered in lexicographical order.
Sample 1 Input
ababba
Sample 1 Output
6 5 0 2 4 1 3
Sample 2 Input
aaaa
Sample 2 Output
4 3 2 1 0
Sample 3 Input
ppppplppp
Sample 3 Output
9 5 8 4 7 3 6 2 1 0
nn
2 1 0