String algorithms · 41 / 53
Suffix arrays, LCP, suffix trees and FM-indexes
Understand → trace → implement → justify
1 min reading · allow extra time for practiceA suffix array orders suffix start indices lexicographically. Copying full suffix strings can require quadratic storage; use index-based construction. Doubling sorts rank pairs for lengths1,2,4…; radix-assisted and comparison-sorted versions have different bounds.
LCP stores common-prefix lengths of neighbouring suffixes. Kasai reuses a match length decreased by at most one and scans linearly. Repeated and distinct substring problems follow from LCP. Suffix trees compress paths and permit linear construction under suitable assumptions, though implementation is intricate.
BWT/FM-index backward search uses rank/select for compressed indexing. Search costs depend on pattern length, output and memory behaviour, not a universal instant lookup. Suffix automata are another distinct substring-index structure.
A worked trace
banana suffixes sort as a,ana,anana,banana,na,nana with indices[5,3,1,0,4,2]; ana prefixes two suffixes.
Cost and assumptions
Suffix arrays store O(n) indices; simple binary pattern search O(m log n), with LCP-aware improvements.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
# Small-input oracle, NOT an efficient construction algorithm.
def suffix_array_oracle(text):
return sorted(range(len(text)),key=lambda i:text[i:])
assert suffix_array_oracle("banana") == [5,3,1,0,4,2]TEST YOUR UNDERSTANDING
Your turn
Why is this oracle unsuitable for large production texts?
Reveal the reasoning
Its key function copies all suffixes, totalling Θ(n²) characters. Do not confuse a small-input oracle with optimised construction.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
MIT 6.046J · Design and Analysis ↗