Suffix arrays and trees

Index the TEXT once; then find any pattern in O(m log n). A suffix array = the sorted order of all the text's suffixes.

Why sorting suffixes works

• Every substring is the prefix of some suffix
• Sort the suffixes → occurrences of a pattern form a CONTIGUOUS block
• Two binary searches bracket the block: O(m log n) per query
• Store just n start indices, not the suffixes → O(n) space

Watch binary search on suffixes

Sorted suffixes of 'banana'; search for 'ana'. Orange = midpoint compared · block found = positions [1, 3].

Index amortizes over queries

Build costs 12ms upfront; each query is tiny. Rescan re-reads the text every time. Crossover ≈ 50 queries.

Prefix doubling + LCP

• Build: rank on first 1, then 2, 4, … chars, reusing prior ranks → O(n log²n)
• LCP array (Kasai, O(n)): longest common prefix of adjacent sorted suffixes
• Longest repeated substring = max(LCP); longest common substring; distinct count
• Suffix array + LCP = a suffix tree at ¼ the memory (4n vs ~20n bytes)

Takeaway

Indexing: pay a fixed build to make repeated queries cheap — worth it past the crossover. Genomics (FM-index), full-text search, BWT compression all live here. Next: Aho-Corasick — one automaton for thousands of patterns.