Suffix arrays and suffix automata: Definition & Examples

A suffix array stores the starting offsets of a sequence’s nonempty suffixes in lexicographic order. A suffix automaton is a deterministic graph that recognises the sequence’s suffixes and can test any contiguous substring by following a path from its initial state. Both preprocess the sequence being searched. A quant developer investigating a fixed order-book replay can build an index once, then query it for different sequences of adds, cancels and trades.

One search, two kinds of position

Take BANANA as a toy sequence and number its positions from 0. The suffix array is

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

, corresponding to A, ANA, ANANA, BANANA, NA, NANA. The order is alphabetical, with a shorter string first when it is a prefix of the longer one.

Every occurrence of ANA starts a suffix whose first three symbols are ANA. Those suffixes occupy one contiguous block in sorted order. Two binary searches find the first suffix whose prefix is at least the pattern and the first whose prefix is greater, comparing up to the pattern length each time. Here the matching ranks are

[1,3)

. The interval width gives two matches, and the entries at those ranks give starts 3 and 1, in suffix order. The matches overlap at position 3. Manber and Myers, Section 2

BANANA has suffix starts 5, 3, 1, 0, 4, 2 in sorted order. ANA matches at ranks 1 and 2, with starts 3 and 1. ANA and NA both end at positions 3 and 5.

The suffix array groups the starts of one pattern. The automaton groups different patterns with identical end positions.

The automaton merges nonempty substrings into the same state precisely when their sets of inclusive end positions agree. ANA starts at 1 and 3, while NA starts at 2 and 4. Both end at 3 and 5, so their paths reach the same state. At each of those endpoints, the text left to read is the same for either pattern. Equal counts alone are insufficient. For instance, AN also occurs twice, but its matches end at 2 and 4. Crochemore and Lecroq, Section 1.3.5

To test substring membership, follow one labelled edge per pattern symbol from the initial state. A missing edge means the pattern is absent. A complete path means the substring exists, and reaching a terminal state additionally means it occurs at the end of the text. The path for AN reaches a nonterminal state. The path for NA reaches a terminal state because one occurrence ends at the final index.

Membership, count and reporting

Let $n$ be the sequence length, $m$ the length of a nonempty query pattern and $k$ the number of matches. Assume comparisons between encoded symbols take constant time.

Suffix array. One binary search and a match check answer membership. Two searches give the count in $O(m\log n)$ time, since one comparison can inspect $m$ symbols. Reporting adds $O(k)$ to read the interval. A search augmented with precomputed longest-common-prefix information reduces the search portion to $O(m+\log n)$ . After ranking the single symbols, a rank-doubling construction sorts pairs of integer ranks in linear time per round, giving $O(n\log n)$ construction time and $O(n)$ space. Manber and Myers, Sections 2–4
Suffix automaton. With constant-time transitions, a pattern walk answers membership in $O(m)$ . For a fixed, small alphabet, an append-by-symbol construction runs in $O(n)$ total time. Dense transition tables reserve one slot per symbol at every state. With a large alphabet of size $\sigma$ , sparse ordered maps keep storage linear in the number of states and edges, but can raise construction time to $O(n\log(\sigma+1))$ and the walk to $O(m\log(\sigma+1))$ . Crochemore and Lecroq, Table 1.1 and Section 1.3.5

The automaton walk identifies a state. To count or report matches efficiently, build an auxiliary index after construction. Give each text prefix’s state a marker for its end position, then make a tree by using each state's suffix link as its parent. A link moves to the next shorter suffix class. The markers below the pattern’s state, including any on the state itself, are exactly the pattern’s end positions. Collecting markers in depth-first order puts each subtree’s markers in a contiguous slice. Store the slice boundaries per state in a linear pass, then use the width to count in constant time after the walk or read the slice in

O(k)

to report starts. For a reported end

e

, the start is

e-m+1

. Crochemore’s suffix-link tree construction

A fixed replay with many pattern queries is where preprocessing can pay off. For one known pattern in a fresh stream, Knuth–Morris–Pratt preprocesses the pattern and scans the stream once. In a replay index, choose symbols and boundaries before building it. If sessions are concatenated, insert a separator excluded from queries so a match cannot silently span the close of one session and the open of the next.

The SelfMadeQuant lesson on Python’s built-in data structures covers the left and right insertion points used to bracket a match interval. The full lesson requires membership.

Sources

Udi Manber and Gene Myers (1993). Suffix Arrays: A New Method for On-Line String Searches. Sorted suffix offsets, prefix interval queries and rank-doubling construction.
Maxime Crochemore and Thierry Lecroq. Text Searching and Indexing. Indexing costs, the minimal suffix automaton and append construction.
Maxime Crochemore (1986). Transducers and Repetitions. Suffix links, their tree structure and the distinction between factor and suffix automata.

One search, two kinds of position

Membership, count and reporting

Sources

Related terms

Array

Binary search

Knuth Morris Pratt algorithm