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
Use Cases
Frequently Asked Questions
From the Blog
JavaScript Array Methods You Should Know
Master essential JavaScript array methods like map, filter, reduce, find, and forEach to transform and query data cleanly without manual loops.
Read More ProgrammingPython list vs array.array vs NumPy array
A list stores pointers to objects, array.array stores raw values of one type, and a NumPy array adds vectorised operations over that same contiguous buffer. The choice comes down to whether your data is homogeneous and whether you operate on it element-wise — and mixing Python loops with NumPy throws away the reason to use it.
Read More ProgrammingJavaScript Map, Filter and Reduce Explained
map transforms, filter selects, and reduce combines array items into a single value. Learn these three functional methods to write cleaner, loop-free JavaScript.
Read More ProgrammingWhat Is NumPy and Why Does Python Need It?
NumPy is the foundational Python library for fast numerical computing, giving Python array operations that run at compiled-language speed. This guide explains what NumPy does, its core array object, and why so much of the Python data stack depends on it.
Read More