Linear Suffix Arrays

The LCP array needs a sparse table over the suffix array, so building it is $\Theta(n \log n)$.

Kasai computes the LCP array in $O(n)$, using $height[rk[i]] \ge height[rk[i-1]] - 1$.

SA-IS and DC3 both build the suffix array in $O(n)$.

Doubling with a general comparison sort is $O(n \log^2 n)$.

Replacing the comparison sort with a radix sort on the two rank keys makes doubling $O(n \log n)$.

Every suffix array construction is $\Omega(n \log n)$, by the comparison sorting lower bound.