Suffix Arrays Explained: Fast String Search

A suffix array is a sorted list of every suffix of a string, represented compactly as an array of starting indices rather than the substrings themselves. It’s a way to answer “does this pattern appear in this text, and where” using binary search instead of scanning, and it does so with far less memory overhead than the data structure it’s usually compared against, the suffix tree.

What a suffix is, and why sorting all of them helps

Every position in a string marks the start of a suffix — the substring running from that position to the end of the string. For the string banana, the suffixes are banana, anana, nana, ana, na, and a. A suffix array doesn’t store these substrings directly; it stores the starting index of each suffix, sorted according to how the suffixes compare alphabetically:

Suffixes of "banana" sorted:
a       (index 5)
ana     (index 3)
anana   (index 1)
banana  (index 0)
na      (index 4)
nana    (index 2)

Suffix array: [5, 3, 1, 0, 4, 2]

Once every suffix is sorted, searching for whether a pattern exists in the text becomes a binary search problem: any occurrence of a pattern in the text is, by definition, the prefix of some suffix, and because all suffixes are sorted, every suffix that starts with your pattern sits in one contiguous block of the array. Binary search finds the edges of that block in logarithmic time, the same principle behind searching any sorted structure — see binary search trees explained for the general idea applied to a different structure.

How suffix array search compares to other string algorithms

Algorithms like KMP and Rabin-Karp are built to search for one pattern in one pass over the text, in linear time relative to the text length. That’s efficient for a single search, but if you need to search the same text repeatedly for many different patterns, redoing a linear scan every time wastes the fact that the text itself never changes between searches.

A suffix array flips the cost structure: building it takes some upfront work, but once built, each subsequent search against that same text is a fast binary search rather than a fresh scan. It’s the same tradeoff behind building an index in a database — pay a cost once, then benefit from it on every query afterward, rather than paying the full scan cost every single time.

Suffix array vs suffix tree

A suffix tree stores the same information — every suffix of a string — but as an actual tree structure where common prefixes are shared along tree paths, similar in spirit to how a trie shares prefixes across stored strings. Suffix trees support some queries even faster than a suffix array’s binary search, but at a real cost: each node needs pointers to its children, and that per-node overhead adds up to substantially more memory than a suffix array, which is just a flat array of integers.

	Suffix array	Suffix tree
Structure	Sorted array of suffix start indices	Tree with shared prefix paths
Memory overhead	Low — one integer per suffix	Higher — per-node pointers and structure
Pattern search	Binary search, O(m log n) for pattern length m	Direct tree walk, often O(m)
Construction complexity	More involved to build efficiently	More involved, larger constant factors
Practical use	Preferred in memory-constrained or large-text settings	Preferred when raw query speed matters more than memory

In practice, suffix arrays are the more commonly deployed structure precisely because of that memory difference — for genome-scale text or large document corpora, the gap between “an array of integers” and “a tree of pointer-laden nodes” is often decisive.

Augmenting with the LCP array

Suffix arrays are frequently paired with a longest common prefix (LCP) array, which records how many leading characters two adjacent suffixes in the sorted order share. This addition speeds up several operations — finding the longest repeated substring in a text, or narrowing binary search ranges — without giving up the suffix array’s memory advantage over a full tree. It’s a common pattern in algorithm design generally: keep the compact primary structure, and add a small auxiliary array to recover some of the speed a heavier structure would otherwise provide.

Where this shows up in practice

Suffix arrays underpin full-text search over large, mostly static bodies of text — genome sequence matching, compressed full-text indexes, and some implementations of the Burrows-Wheeler transform used in data compression all build on the same sorted-suffix idea. They’re a good fit whenever the text is large, queried repeatedly, and doesn’t change often enough to make rebuilding the index a bottleneck — a very different profile from streaming or single-pass text search, where an algorithm like KMP that needs no preprocessing of the text itself is the better fit. For a sense of how the runtime cost is usually expressed and compared across approaches like this, see what Big O notation is.

The takeaway

A suffix array turns every suffix of a string into a sorted, compact index that supports binary-search pattern matching, trading a one-time construction cost for fast repeated queries against the same text. It gives up a little raw query speed compared to a suffix tree, but in exchange uses far less memory, which is why it’s the more common choice for large-scale text search in practice. Pair it with an LCP array when you need to recover some of that speed without giving up the compact representation.