10316: CF EDU - Suffix Array - Step 4 - A. Suffix Array and LCP
[Creator : ]
Description
Try to implement the algorithm of Kasai, Arimura, Arikawa, Lee and Park find the values of lcp for the suffix array.
Build a suffix array for a given string $s$, for each two adjacent suffixes find the length of longest common prefix.
Input
First line holds a single string $s$ of length $n\ (1≤n≤400,000)$. String consists of small english letters.
Output
In the first line print $n+1$ distinct integers, indices of first characters of suffixes of $s$, ordered in lexicographical order.
In the second line print $n$ integers, lengths of longest common prefixes.
Sample 1 Input
ababba
Sample 1 Output
6 5 0 2 4 1 3
0 1 2 0 2 1
Sample 2 Input
aaaa
Sample 2 Output
4 3 2 1 0
0 1 2 3
Sample 3 Input
ppppplppp
Sample 3 Output
9 5 8 4 7 3 6 2 1 0
0 0 1 1 2 2 3 3 4
nn
2 1 0
0 1