cho.shSuffix Array
No attempts yetTime limit3sMemory limit256 MBProblem
The suffix array of a string S lists the starting positions of every suffix of S in lexicographic order. Positions are counted from 1. For example, if S is banana, there are six suffixes.
| Suffix | Starting position |
|---|---|
| banana | 1 |
| anana | 2 |
| nana | 3 |
| ana | 4 |
| na | 5 |
| a | 6 |
Sorted lexicographically, they come out in this order.
| Suffix | Starting position |
|---|---|
| a | 6 |
| ana | 4 |
| anana | 2 |
| banana | 1 |
| na | 5 |
| nana | 3 |
Reading the starting positions down the sorted table gives [6, 4, 2, 1, 5, 3], the suffix array of banana.
The LCP array is built on top of the suffix array. For each suffix in sorted order it stores the length of the LCP (Longest Common Prefix) shared with the suffix immediately before it. The first suffix has nothing before it, so its value is undefined. For banana the LCP array is [x, 1, 3, 0, 0, 2].
Given a string of length at most 500000, write a program that computes its suffix array and its LCP array.
Input
The first line contains a string S made up of lowercase letters only. The length of S is at most 500000.
Output
Print the suffix array on the first line and the LCP array on the second line, separating values with a single space. Print the first value of the LCP array as x.