Lesson 8 · Advanced structures and algorithms

Suffix Arrays

A Suffix Array is a memory-efficient sorted array of all suffixes of a string, enabling fast substring searches and longest repeated substring queries.

Sorted Suffixes, Stored as Integers

A suffix array is an array of the starting positions of every suffix of a string, sorted by the lexicographic order of the suffixes themselves. For a text of length n, it holds n integers and nothing else.

The critical point is that the suffixes are not stored. Storing them would need O(n²) characters, since the suffixes of a length-n string total n(n+1)/2 characters. Only their starting positions are kept, and the original text is retained alongside — any suffix is then recoverable as a slice from its position to the end.

For the text banana, the suffixes sorted lexicographically are a, ana, anana, banana, na, nana, whose starting positions are 5, 3, 1, 0, 4, 2. That list of six integers is the suffix array.

The reason this is useful rests on one observation, the same one that motivates suffix trees: every substring of the text is a prefix of some suffix. So questions about substrings become questions about prefixes of the sorted suffix list — and a sorted list can be binary searched.

Space is the headline advantage. The array is 4 bytes per character with 32-bit integers, or 8 with 64-bit, against a suffix tree's 10 to 20 bytes per character. That is often a twenty-fold reduction, and it is contiguous memory rather than scattered nodes, so traversing it is cache-friendly in a way pointer-chasing is not.

This is why suffix arrays displaced suffix trees in practice despite the tree's better asymptotic search bound. The constant factors and memory behaviour dominate at the scales where these structures are actually used.

n integers: the starting positions, sorted by their suffixes
The suffixes themselves are never stored — only positions plus the text
Every substring is a prefix of some suffix, so sorting enables search
4–8 bytes per character against a suffix tree's 10–20

Searching by Binary Search

Because the suffixes are in sorted order, all suffixes beginning with a given pattern occupy a contiguous block of the array. Finding a pattern means locating that block.

A standard binary search does it. At each step, compare the pattern against the suffix at the midpoint position — a comparison costing up to O(m) for a pattern of length m — and narrow the range accordingly. With O(log n) steps, a search costs O(m log n).

Using lower bound and upper bound searches finds the block's two edges, and every position between them is an occurrence. The count of occurrences is the difference of the two bounds, available in O(1) once the block is located, and the positions themselves are read directly from the array.

Compare this to the alternatives. A suffix tree searches in O(m), independent of n, which is asymptotically better. KMP searches in O(n + m) per pattern, which is worse whenever the text is large and searched repeatedly.

So the suffix array sits between them: it gives up the tree's O(m) for an extra log factor, and buys a structure a fraction of the size. For a one-gigabyte text, log n is about 30 — a modest multiplier against a twentyfold memory saving.

That log factor can be removed. Augmenting the array with the LCP information described next allows the comparisons to skip characters already known to match, bringing the search to O(m + log n). With that refinement the practical gap to a suffix tree largely disappears, which is the final reason suffix arrays win in production.

Suffixes sharing a prefix form a contiguous block in the array
Binary search locates it at O(m log n) — m per comparison
Lower and upper bounds give the count and all positions
With LCP augmentation the search improves to O(m + log n)

The LCP Array

The LCP array — longest common prefix — stores, for each position i in the suffix array, the length of the longest prefix shared by the suffix at i and the suffix at i−1. It is n integers alongside the suffix array, and it is what turns a sorted list into a structure capable of answering the questions a suffix tree answers.

For banana, the sorted suffixes a, ana, anana, banana, na, nana share prefixes of length 0, 1, 3, 0, 0, 2 with their predecessors. Note the value 3 between ana and anana — adjacent suffixes in sorted order tend to share long prefixes, which is exactly the information being captured.

Kasai's algorithm computes the whole LCP array in O(n) given the suffix array and its inverse, which is a genuinely elegant result. The idea is to process suffixes in the order they appear in the text rather than in the array, because the LCP value for a suffix starting at position i is at least one less than the value for the suffix at i−1. That monotonicity means the total number of character comparisons across the whole computation is bounded by 2n, so no comparison work is repeated.

What the array enables is the important part. The longest repeated substring is simply the maximum value in the LCP array — a repeated substring appears in at least two suffixes, those suffixes are adjacent or near-adjacent in sorted order, and their shared prefix is that substring. One pass over the array answers a question that otherwise requires a suffix tree traversal.

The number of distinct substrings is n(n+1)/2 − sum(LCP), since the total suffix prefixes count every substring with duplicates, and the LCP sum is exactly the duplication.

The longest common substring of two texts is found by concatenating them with a separator, building the suffix array, and taking the maximum LCP value between adjacent suffixes originating from different texts.

Combined with a sparse table for range minimum queries over the LCP array, the shared prefix of any two suffixes becomes answerable in O(1) — which is what makes the suffix array plus LCP array a genuine substitute for a suffix tree.

Suffix array against the alternatives
	Suffix array	Suffix tree	KMP
Space per character	4–8 bytes	10–20 bytes	O(m) for the pattern
Preprocessing	O(n log n) or O(n)	O(n), hard to implement	O(m)
Search	O(m log n), O(m + log n) with LCP	O(m)	O(n) per search
Locality	Contiguous	Pointer chasing	—
Best for	Large texts, many queries	Structural queries	One pattern, streaming

LCP[i] is the prefix shared by suffixes i and i−1 in sorted order
Kasai's algorithm computes it all in O(n)
The maximum LCP value is the longest repeated substring
With a sparse table, any two suffixes' shared prefix is O(1)

Key reference

Terms, operations, and practical uses

Fundamentals

Suffix ArrayAn array of integers representing the starting indices of all suffixes of a string, sorted in lexicographical order.
Memory ProfileRequires exactly O(N) integers to store, making it vastly more practical than generating all string copies.
Substring PropertyEvery single substring of the text is simply a prefix of one of the suffixes in the suffix array.

Operations

Pattern MatchingBecause the suffixes are sorted, finding a pattern of length M in text of length N takes O(M log N) via Binary Search.
LCP ArrayThe Longest Common Prefix array stores the length of the matching prefix between adjacent suffixes in the sorted Suffix Array.
Repeated SubstringsThe maximum value in the LCP array instantly identifies the longest substring that appears at least twice in the text.

Construction

Naive SortExtracting all suffixes and running QuickSort takes O(N² log N) due to string comparison overhead.
Prefix DoublingSorts prefixes of length 1, then 2, 4, 8, etc., updating a rank array. Constructs the Suffix Array in O(N log² N).
DC3 / SA-ISAdvanced algorithms capable of constructing the Suffix Array in strictly O(N) linear time.

Implementation

Build the suffix array for banana

def build_suffix_array(s):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort()
    return [idx for suffix, idx in suffixes]
print('SA:', build_suffix_array('banana'))

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> buildSuffixArray(string s) {
    vector<pair<string, int>> suffixes;
    for (int i = 0; i < s.length(); i++)
    suffixes.push_back({s.substr(i), i});
    sort(suffixes.begin(), suffixes.end());
    vector<int> sa;
    for (auto& p : suffixes) sa.push_back(p.second);
    return sa;
}
int main() {
    vector<int> sa = buildSuffixArray("banana");
    cout << "SA: [";
    for(size_t i = 0; i < sa.size(); i++) {
        if (i) cout << ", ";
        cout << sa[i];
    }
    cout << "]\n";
}

import java.util.*;
public class Main {
    public int[] build(String s) {
        String[] suffixes = new String[s.length()];
        Integer[] indices = new Integer[s.length()];
        for (int i = 0; i < s.length(); i++) {
            suffixes[i] = s.substring(i);
            indices[i] = i;
        }
        Arrays.sort(indices, (a, b) -> suffixes[a].compareTo(suffixes[b]));
        return Arrays.stream(indices).mapToInt(i->i).toArray();
    }
    public static void main(String[] args) {
        System.out.println("SA: " + Arrays.toString(new Main().build("banana")));
    }
}

Watch it run

Step through it

Running on text = "banana"

Output

Read all 11 Steps

The string Take 'banana'. A suffix array lists the starting index of every suffix, sorted alphabetically.
All suffixes Six suffixes: banana(0), anana(1), nana(2), ana(3), na(4), a(5).
Sort them Sorted alphabetically: a(5), ana(3), anana(1), banana(0), na(4), nana(2).
That is the array The suffix array is just those indices: [5, 3, 1, 0, 4, 2]. It stores n integers, not n strings.
Why it is compact A suffix tree needs nodes and pointers; a suffix array needs one integer per position. Same queries, far less memory.
Search 'ana' Because the suffixes are sorted, binary search finds a pattern instead of scanning.
Compare Midpoint is index 1, suffix 'anana'. It starts with 'ana', so we have a match — and matches are contiguous in a sorted array.
Expand Neighbours share the prefix too: index 3 gives 'ana'. Both occurrences sit next to each other.
Occurrences 'ana' occurs at positions 1 and 3 in 'banana' — overlapping, which a naive scan often misses.
Cost Binary search over n suffixes with an O(m) comparison gives O(m log n) — no preprocessing per query.
With LCP Pairing the array with an LCP array (longest common prefix of adjacent suffixes) speeds this to O(m + log n) and powers longest-repeated-substring queries.

Building It

Construction is where the interesting algorithmic work sits, and there are three approaches worth distinguishing.

Naive sorting generates all n suffixes and sorts them with a standard comparison sort. Each comparison costs up to O(n), so the total is O(n² log n) — and it also needs O(n²) memory if the suffixes are materialised. Unusable beyond small inputs, but worth stating as the baseline the others improve on.

Prefix doubling, the Manber–Myers approach, is the practical method to know. It sorts the suffixes by their first character, then their first 2 characters, then 4, 8, and so on, doubling each round. The key trick is that after sorting by the first k characters, each suffix can be given a rank, and sorting by the first 2k characters requires only comparing pairs of ranks — an O(1) comparison rather than an O(k) one, because the ranks already encode the first k characters.

With log n doubling rounds and an O(n log n) sort in each, the total is O(n log² n); replacing the comparison sort with radix sort on the rank pairs gives O(n log n). This is the algorithm most competitive programmers implement, because it is short and fast enough for essentially any input size.

Linear-time construction exists — the DC3 / skew algorithm and the SA-IS algorithm both achieve O(n). SA-IS is the one used in practice; it is what most production libraries implement, and it is fast in constant factors as well as asymptotically. Both are considerably harder to implement than prefix doubling, which is the usual reason to reach for a library rather than write one.

For interview purposes, the expected answer is usually to describe prefix doubling and to know that O(n) construction exists. For production use, the answer is to use an existing implementation — sais, the SDSL library, or the language's equivalent.

Where these structures actually get used: bioinformatics aligns sequencing reads against reference genomes, indexing the genome once and querying it billions of times. Data compression relies on the closely related Burrows–Wheeler transform, which is computed directly from the suffix array and underlies bzip2. And full-text search engines use suffix arrays or the derived FM-index, which compresses the structure further while remaining searchable — the direction the field has moved since.

Naive suffix sorting is O(n² log n) — the baseline to improve on
Prefix doubling sorts by ranks, giving O(n log n) with radix sort
SA-IS and DC3 achieve O(n) and are what libraries implement
Used in genome alignment, bzip2's BWT, and full-text indexes