P10469 Suffix Array

The suffix array (SA) is an important data structure, usually implemented using the doubling method or the DC3 algorithm, which is beyond the scope of our discussion. In this problem, we want to build a simple $O(n\log^2 n)$ method for constructing the suffix array using quicksort, hashing, and binary search. More specifically, given a string $S$ of length $n$ (indexed from $0 \sim n-1$), we can use an integer $k(0 \le k < n)$ to represent the suffix $S(k \sim n-1)$ of $S$. Sort all suffixes of $S$ in lexicographical order, and let the suffix with rank $i$ be denoted as SA[i]. In addition, for the suffix ranked $i$ and the suffix ranked $i-1$, let the length of their longest common prefix be denoted as Height[i]. In particular, define Height[0] = 0. Your task is to output the two arrays SA and Height.

Input a string whose length does not exceed $300000$. The string consists of lowercase letters.

The first line contains the array SA, where adjacent integers are separated by exactly $1$ space. The second line contains the array Height, where adjacent integers are separated by exactly $1$ space.

Translated by ChatGPT 5