Suffix Array
String indexing data structure
A suffix array is a sorted array of all the starting indices of the suffixes of a string, providing a compact data structure for fast substring search and other string-processing tasks.
Definition
A suffix array is a sorted array of all the starting indices of the suffixes of a string, providing a compact data structure for fast substring search and other string-processing tasks.
Overview
Given a string S, its suffix array is constructed by listing every suffix of S and sorting those suffixes in lexicographic order, storing only the starting index of each suffix rather than the suffix text itself. This simple integer-array representation requires only O(n) space (with a small constant factor, unlike a suffix tree), making it far more memory-efficient in practice for large texts such as genomic sequences or search-engine corpora. A naive construction using standard sorting takes O(n^2 log n) time due to the cost of comparing suffixes, but specialized linear and near-linear algorithms — such as the DC3/skew algorithm and prefix-doubling approaches — build a suffix array in O(n) or O(n log n) time. Once built, binary search over the sorted suffix array allows substring search in O(m log n) time, where m is the pattern length; augmenting the suffix array with an LCP (longest common prefix) array, which records the length of the shared prefix between lexicographically adjacent suffixes, enables many suffix-tree-equivalent queries (including O(m) substring search) while retaining the array's compact footprint. Because of their favorable space-to-functionality tradeoff, suffix arrays have largely supplanted suffix trees in production string-processing systems, including bioinformatics tools for genome indexing and alignment (such as the Burrows-Wheeler transform-based aligners used for short-read sequencing), full-text search engines, data compression algorithms (the Burrows-Wheeler transform itself is computed via a close variant of suffix array construction), and plagiarism and text-similarity detection tools. The combination of a suffix array with its LCP array is often referred to as an "enhanced suffix array," since together they recover essentially all the algorithmic power of a suffix tree at a fraction of the memory cost.
Key Concepts
- Sorted array of starting indices of all suffixes of a string
- Requires only O(n) space with a small constant factor
- Built in O(n) or O(n log n) time via DC3/skew or prefix-doubling algorithms
- Supports substring search via binary search in O(m log n) time
- Paired with an LCP array to recover near-suffix-tree query power
- More memory-efficient in practice than an equivalent suffix tree
- Basis of the Burrows-Wheeler transform used in data compression
- Widely used in genome alignment tools for short-read sequencing