Algorithms and data structures · Intermediate

Suffix arrays: search a lexicographic order of starting positions

Order the suffixes of banana and use a contiguous matching interval, while separating index size from construction and comparison costs.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Store starts instead of copied strings
  2. Find the matching rank interval
  3. Separate construction, storage and querying
  4. Add LCP only when needed
  5. Ask Logeia about this articleCheck your understanding

Store starts instead of copied strings

A suffix array SA lists starting positions of all suffixes in lexicographic order. The original text is retained, so the suffix strings do not need to be copied into the index. For banana, the order is a, ana, anana, banana, na, nana, giving zero-based SA=[5,3,1,0,4,2]. An index into SA is a lexicographic rank, while the stored value is a position in the original text. Confusing those two coordinate systems produces incorrect search results even when the suffixes themselves were sorted correctly.

Find the matching rank interval

Searching for ana finds suffixes ana and anana at suffix-array ranks one and two. Their text positions are three and one, respectively. If results must be returned in increasing text-position order, that is an additional output requirement. Binary searches can find the boundaries of the contiguous rank interval whose suffixes start with the pattern. The upper-bound comparison needs a defined treatment of equality through the pattern’s length; comparing entire suffixes for ordinary string equality would miss the longer anana suffix. A prefix match is not an equality of complete strings.

Separate construction, storage and querying

The array of n starting positions occupies O(n) space, but copying every suffix naively costs O(n²) total characters. Sorting positions with comparisons that repeatedly scan long suffixes can also make construction expensive. Dedicated methods, such as doubling prefix ranks, reduce redundant work, but their bounds depend on the exact construction and sorting technique. With ordinary character-by-character comparisons, binary searching a pattern of length m has an O(m log n) basic upper bound. O(log n) comparison operations do not imply O(log n) running time when each operation can inspect up to m characters.

Add LCP only when needed

An LCP array records longest-common-prefix lengths of adjacent sorted suffixes and supports tasks such as analyzing repeated substrings. It can also contribute to faster query comparisons, but those improvements require additional algorithms rather than appearing automatically from the suffix array alone. Text updates can change many ranks, so this is naturally a static-index design. If construction adds a sentinel, define its ordering and whether its suffix appears in output. Byte order, Unicode code points and language-specific collation produce different semantics; normalization and mapping returned positions back to the original text require explicit decisions.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path