The classical string matchers (KMP, Rabin-Karp, Z, Boyer-Moore) preprocess a single pattern in O(m) to find it in O(n) text — one pattern, one query. Suffix structures make the opposite trade: preprocess the text itself in O(n), then answer endless pattern queries in O(m) each. The applications multiply: a search engine’s autocomplete, the text editor’s “find all occurrences”, the biologist’s “where does this 30-mer appear in the genome”, the compressor’s “longest previously-seen substring”.

This topic is the stringology of 21st-century text indexing.

Suffix Array

The suffix array SA of a text T of length n is the array of starting indices of all suffixes of T, sorted lexicographically.

T = "banana"
suffixes:
  0: banana     sort       0: a
  1: anana     lexicographically  →  1: ana
  2: nana                            2: anana
  3: ana                             3: banana
  4: na                              4: na
  5: a                               5: nana

SA = [5, 3, 1, 0, 4, 2]

The naive construction is O(n² log n) via Python’s sorted(range(n), key=lambda i: T[i:]) — O(n log n) comparisons, each comparing suffixes in up to O(n) character scans. Two modern constructions build it in O(n):

• SA-IS (Suffix Array Induced Sorting, 2009) — O(n) time, the production-grade default.
• DC3 / Kaňadath-Myers (2003) — O(n) time, the classic theoretical construction.

The suffix array is what most string-index libraries ship today — small enough to fit in memory on commodity hardware; quick to construct; supports any pattern query.

Pattern Matching on the Suffix Array

Find a pattern P in O(|P| + log n) time by binary-searching the suffix array. Two binary searches bracket the range of suffixes that start with P:

            SA = [5, 3, 1, 0, 4, 2]
suffixes sorted: a, ana, anana, banana, na, nana
P = "ana"        ↑    ↑            (range [1,2])
P = "x"          (range empty)

The bracket of O(k) matched suffix indices SA[l..r] contains every occurrence of P. The pattern query is O(|P| + log n + k) — O(|P|) matching, O(log n) binary search, O(k) to report.

LCP Array and Kasai’s Algorithm

The LCP array is a companion of the suffix array: LCP[i] = longest common prefix of suffix[SA[i]] and suffix[SA[i-1]]. The LCP array of "banana":

SA  = [5, 3, 1, 0, 4, 2]
suffix = "a", "ana", "anana", "banana", "na", "nana"
LCP  = [_,  1,  3,  0,  2,  3]

Kasai’s algorithm computes the LCP array in O(n) time, exploiting the fact that removing the first character of a suffix leaves another suffix — so LCP at position i+1 is at least LCP[i] - 1. The key insight: walk leftmost suffix to rightmost, decrement-by-one bound prevents O(n²) work.

The LCP array turns the suffix array from “I can find any pattern” into “I can compute any string invariant based on repeated substrings”.

Suffix Tree

The suffix tree is a compressed trie of all suffixes of T. Each leaf is a suffix end; internal nodes are branching points where suffixes diverge; edges store substrings (not single characters).

T = "banana$"
                              root
                            /  |  \
                           $  banana  na
                            |        |
                          banana    nana
                                       |
                                     banana

Construction: Ukkonen’s algorithm in O(n). Properties:

• Stores all suffixes in O(n) space (compressed edges).
• Supports every operation the suffix array does, plus: longest repeated substring (O(n) traverse to deepest internal node), longest common substring of two strings (O(n+m) to build a generalised suffix tree then deepest internal node tagged with both sources), linear-time matching of any pattern set.

The suffix tree is strictly more powerful than the suffix array — but uses O(n) pointers and is memory-heavy; the suffix array + LCP + a range-minimum sparse table answers all the same queries with smaller cache footprint. Most production systems ship the suffix array form.

Suffix Automaton

The suffix automaton is the minimal DFA that accepts all suffixes of T. Distinct from the suffix tree: it accepts by suffix-class, not by literal suffix; construction is O(n) via the endpos-equivalence relation — two substrings are equivalent iff their sets of end positions in T are equal.

The automaton powers:

• Number of distinct substrings in T — O(n) traversal of state count.
• Longest common substring of two strings — extend the automaton online with new characters; the longest string the automaton accepts after the extension is the LCS.
• Online string matching — feed text characters one at a time; the automaton always knows the longest suffix currently matching P.

A suffix automaton has at most 2n - 1 states and 3n - 4 transitions. The surprising property: the minimal DFA accepting every suffix of a string is smaller than the suffix tree of the same string.

Burrows-Wheeler Transform (BWT)

A close relative: the BWT of T is the last column of the matrix of all rotations of T, sorted lexicographically. Equivalently, the BWT is T[SA[i] - 1] over i = 0..n-1 (modulo $).

All rotations of "banana$" sorted:
  $banana     → BWT[i] = T[SA[i]-1] = a
  a$banan     → a
  ana$ban     → n
  anana$b     → a
  banana$     → $
  na$bana     → a
  nana$ban    → n
                              BWT = "annb$aa"  — readable!

The BWT is reversible (no information lost). The key property: characters preceding similar contexts cluster together — "a" appears together in the output, ideal for run-length encoding and LZ indexing. bzip2 uses the BWT as its first stage; bgzip and the Sina/Bwa alignment tools use it for bioinformatics read indexing.

The BWT is the basis for the FM index (Ferragina-Manzini), the production indexer inside every short-read aligner used in genomics.

Applications

The money observation: a 3-billion-character genome has a 12-billion-byte suffix array (4-byte int indices) and 12GB is barely a single in-memory database today; step queries against it run in microseconds.

Practice Trajectory

1. Build a suffix array of "mississippi" by naive sort. Implement binary search for "issi" and "issp"; report all occurrences.
2. Implement Kasai’s LCP algorithm; verify against the brute-force LCP for the same string. Compare the runtime constants.
3. For a 100KB English text, compute the number of distinct substrings from the LCP array: total = sum over i of (n - SA[i] - LCP[i]). Verify by enumeration if feasible.
4. Implement a suffix automaton build for a string of your choice; count distinct substrings via the state graph; compare with the LCP-based count.
5. Pick a 30-character pattern and a 30MB English corpus. Use the suffix array to find all occurrences; measure the query time and contrast with a naive Python str.find loop.

When It’s the Right Tool