Suffix Array Only

Suffix Array Primer

This page teaches the suffix array itself: suffixes, lexicographic order, rank classes, and why doubling can compare longer prefixes from two known halves.

Reading Contract

This page answers one question: why a suffix array can represent lexicographic order with sorted start indices. After reading, you should be able to connect suffixes, rank, pair keys, and doubling.

Hand-drawn suffix array mental model: string, suffixes, sort, rank, pair key, and final SA
The suffix-array trick is not copying suffix strings; it turns long string comparison into comparison of start indices, ranks, and pair keys.
Read Suffix first, start index second

Every table is about moving start indices; suffix text only helps verify the order.

Core rank names a prefix

Doubling reuses old ranks as pairs instead of comparing whole strings again.

Check Explain sa[i]

You should leave knowing that sa stores sorted start positions, not copied suffix strings.

Why

Original string

Suffix lab

Current round

# start suffix key new rank

C++

Core code

This code shows the doubling skeleton. The point is not memorizing a template, but seeing how ranks name comparable prefixes.

vector<int> buildSuffixArray(string s) {    s += '$';    int n = s.size();    vector<int> sa(n), cls(n);     vector<pair<char, int>> first(n);    for (int i = 0; i < n; i++) first[i] = {s[i], i};    sort(first.begin(), first.end());    for (int i = 0; i < n; i++) sa[i] = first[i].second;    cls[sa[0]] = 0;    for (int i = 1; i < n; i++) {        cls[sa[i]] = cls[sa[i - 1]];        if (first[i].first != first[i - 1].first) cls[sa[i]]++;    }     for (int len = 1; len < n; len <<= 1) {        sort(sa.begin(), sa.end(), [&](int a, int b) {            if (cls[a] != cls[b]) return cls[a] < cls[b];            return cls[(a + len) % n] < cls[(b + len) % n];        });        vector<int> next(n);        next[sa[0]] = 0;        for (int i = 1; i < n; i++) {            pair<int, int> prev = {                cls[sa[i - 1]], cls[(sa[i - 1] + len) % n],            };            pair<int, int> now = {                cls[sa[i]], cls[(sa[i] + len) % n],            };            next[sa[i]] = next[sa[i - 1]] + (prev != now);        }        cls = next;    }    sa.erase(sa.begin());    return sa;}