10313: CF EDU - Suffix Array - Step 2 - A. Suffix Array - 2
[Creator : ]
Description
This task is the same as the previous one, but the length of string is larger. Try to write as efficient an algorithm as possible.
Build a suffix array for the given string $s$.
Input
Input contains a single string $s$ of length $n\ (1≤n≤400,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