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.

The Substring Problem

Finding if a pattern exists in a massive text, or finding the longest repeated substring, is computationally heavy. A Suffix Array addresses this by generating every possible suffix of the text (e.g., 'banana', 'anana', 'nana') and sorting them lexicographically.

Binary Search on Text

Once the suffixes are sorted alphabetically, any substring of the original text will appear as a prefix to one of these suffixes. We can therefore use a standard O(log N) binary search over the Suffix Array to instantly locate any pattern within a massive document.

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.

Code example

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 <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;
}

import java.util.*;

class SuffixArray {
    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();
    }
}

Inputtext = "banana"

OutputSA: [5, 3, 1, 0, 4, 2]

Example

Run the example step by step

Output

The LCP Array

A Suffix Array is almost always paired with a Longest Common Prefix (LCP) array, which stores how many characters the adjacent sorted suffixes share. The maximum value in the LCP array instantly reveals the longest repeated substring in the original text.

Construction Algorithms

A naive sort of all suffixes takes O(N² log N) time, which is too slow. Advanced algorithms, such as Prefix Doubling, sort the prefixes by comparing lengths of 1, 2, 4, and 8, constructing the array in O(N log² N) or even strictly O(N) time.