Structure

SA[i] = starting index of i-th smallest suffix. LCP array often paired: LCP[i] = longest common prefix of SA[i], SA[i-1].

Advertisement

O(N log² N) construction

Sort by first 1 char. Then by first 2 chars using previous ranks. Then by 4, 8, … Each round O(N log N).

Advertisement

O(N) SA-IS

Ge et al. Skew algorithm. Linear time. Complex but standard in production (SDSL library).

Applications

Substring search: binary search on suffix array. O(M log N). Common substring problems. FM-index basis.