Suffix Array Construction using Quick Sort, Hashing and Binary Search

This problem requires you to compute two arrays from a given string S of length n:

• Suffix Array (SA) - an array where SA[i] is the starting index of the i-th lexicographically smallest suffix of S.
• Height Array - an array where Height[i] (for i > 0) is the length of the longest common prefix (LCP) between the suffixes starting at SA[i] and SA[i-1]. For convenience, define Height[0] = 0.

You are asked to build these arrays using an approach with an overall complexity of \(O(n \log^2 n)\). The intended solution should use quick sort (by implementing a custom comparator), hashing (via a rolling hash), and binary search to compute LCP values efficiently.

The problem statement, in formula form, is as follows:

Given a string \(S\) (with indices \(0 \leq i \leq n-1\)), each suffix of \(S\) can be represented by an integer \(k\) (where \(0 \leq k < n\)) corresponding to the suffix \(S[k \sim n-1]\). When all suffixes are sorted in lexicographical order, let \(SA[i]\) denote the starting index of the i-th suffix, and for \(i \geq 1\) define \(Height[i]\) as:

\[ Height[i] = LCP(SA[i], SA[i-1]) \]

Your task is to output the two arrays.

inputFormat

The input consists of a single line containing the string S.

outputFormat

Output two lines:

• The first line contains n space-separated integers forming the suffix array (SA).
• The second line contains n space-separated integers forming the height array, where the first element is 0.

sample

banana

5 3 1 0 4 2
0 1 3 0 0 2