Suffix Arrays — Compact String Indexing

What it is

// For s = "banana":
// Suffixes: banana(0), anana(1), nana(2), ana(3), na(4), a(5)
// Sorted: a(5), ana(3), anana(1), banana(0), na(4), nana(2)
// SA = [5, 3, 1, 0, 4, 2]

Substring search

Binary search suffix array for pattern P. O(P × log N). Way better than naive O(N × P).

Build in O(N log² N)

Sort suffixes by first 1 char, then 2, then 4… doubling. Radix sort each pass. O(N log N) with clever radix.

LCP array

Longest Common Prefix between adjacent suffixes in SA. Enables O(1) LCP queries after O(N) preprocessing.