a suffix array

A suffix tree is powerful but bulky. The suffix array is the same idea flattened into a plain list of numbers. Take every suffix of a string, sort all of them into alphabetical order, and write down just their starting positions in that sorted order. That short array of integers — no tree, no pointers — captures the lexicographic structure of all suffixes and supports fast pattern search and much more, in a fraction of the memory.

Formally, the suffix array SA of a string S of length n is a permutation of the positions 0..n-1 such that the suffixes starting at SA[0], SA[1], ..., SA[n-1] are in increasing lexicographic (dictionary) order. For "banana" the sorted suffixes are "a", "ana", "anana", "banana", "na", "nana", so SA = [5,3,1,0,4,2]. Because the suffixes are sorted, every occurrence of a pattern P corresponds to a contiguous block of the array (all suffixes that start with P sit together), so you can find that block with two binary searches, giving O(m log n) matching — or O(m + log n) with an auxiliary LCP array. Building the suffix array naively by sorting strings is O(n^2 log n), but specialized algorithms (prefix doubling in O(n log n), or the SA-IS and DC3 algorithms in O(n)) construct it efficiently. The array uses only O(n) integers, perhaps 4 bytes each, far less than a suffix tree.

Suffix arrays are the workhorse behind full-text search indexes, the Burrows-Wheeler transform (the heart of bzip2 and the FM-index used in genome aligners), longest-common-substring queries, and counting distinct substrings. Paired with its companion the LCP array, a suffix array does essentially everything a suffix tree does, with better constants and far better cache behavior, which is why it dominates in practice. The trade-off is conceptual: some operations are more natural to describe on a tree, and you reconstruct that tree-like reasoning from the array plus LCP information rather than reading it off directly.