Advanced · Module 19 · Lesson 4 of 4
Suffix arrays in practice
A suffix array lists the starting positions of a text's suffixes in sorted order. With the LCP array beside it, it answers substring search, repeated substrings and distinct-substring counts, and it underlies genome search tools.
By the end you can
- Build a suffix array by prefix doubling and an LCP array with Kasai's algorithm
- Search for a pattern by binary search over the suffix array
- Solve repeated-substring and distinct-substring problems with the LCP array
Builds on KMP and prefix functions, Binary search without off-by-one bugs.
01 · A question first
A genome has three billion letters, and a sequencing machine produces millions of short reads that must each be located in it. Searching the genome once per read is out of the question. Sort every suffix of the genome once, and each read becomes a binary search. How can three billion suffixes be sorted, and stored, at all?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Sorting every suffix
- Searching
- The LCP array
- Building it efficiently
- Suffix arrays or something simpler?
- Where they run
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem