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.