Suffix Array

The sorted order of all suffixes of a string, stored as an array of starting positions. Paired with the LCP array, it answers most substring questions with far less memory than a suffix tree.

s = banana
sa  = [5, 3, 1, 0, 4, 2]      suffixes: a, ana, anana, banana, na, nana
lcp = [-, 1, 3, 0, 0, 2]      lcp[i] = LCP(sa[i-1], sa[i])

Construction — prefix doubling, $O(n{\log }^{2}n)$

vector<int> suffixArray(string s) {
    s += '\x01';                                   // sentinel, smaller than everything
    int n = s.size();
    vector<int> sa(n), rank_(n), tmp(n);
    iota(sa.begin(), sa.end(), 0);
    for (int i = 0; i < n; i++) rank_[i] = s[i];
 
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rank_[a] != rank_[b]) return rank_[a] < rank_[b];
            int ra = a + k < n ? rank_[a + k] : -1;
            int rb = b + k < n ? rank_[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
        rank_ = tmp;
    }
    return vector<int>(sa.begin() + 1, sa.end());   // drop the sentinel
}

Replacing sort with a two-pass radix sort gives $O(n\log n)$. SA-IS and DC3 give $O(n)$ but are much longer.

The doubling idea is exactly the KMR algorithm.

LCP array — Kasai, $O(n)$

vector<int> kasai(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank_(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank_[sa[i]] = i;
    for (int i = 0, k = 0; i < n; i++) {
        if (rank_[i] == 0) { k = 0; continue; }
        int j = sa[rank_[i] - 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k]) k++;
        lcp[rank_[i]] = k;
        if (k) k--;
    }
    return lcp;
}

What SA + LCP answers

Query	Method	Cost
Does pattern $p$ occur?	binary search the SA	$O(|p|\log n)$
Number of occurrences of $p$	two binary searches	$O(|p|\log n)$
Number of distinct substrings	$\frac{n(n+1)}{2}-\sum \mathrm{lcp}[i]$	$O(n)$
Longest repeated substring	$\max \mathrm{lcp}[i]$	$O(n)$
Longest common substring of two strings	concatenate with a separator; max lcp across the boundary	$O(n)$
LCP of any two suffixes	RMQ over the LCP array	$O(1)$ with a sparse table
$k$-th lexicographic substring	walk the SA with lcp	$O(n)$
Compare two substrings	LCP query + one character	$O(1)$
Longest common substring of $k$ strings	concatenate with distinct separators; sliding window over the SA	$O(n\log n)$

The LCP interval structure

The LCP array implicitly encodes a suffix tree: an internal node of the suffix tree corresponds to a maximal interval of the SA whose minimum LCP equals that node’s string depth. Building this “LCP interval tree” (with a monotonic stack) lets you run suffix-tree algorithms without a suffix tree.

This is why “suffix array + LCP” is usually the right answer: it has the power of a suffix tree at a fraction of the memory and the implementation effort.

Construction methods

Method	Time	Lines	When
Sort suffixes naively	$O(n^2\log n)$	3	$n\le 1000$
Prefix doubling + sort	$O(n{\log }^{2}n)$	~20	$n\le 10^5$
Prefix doubling + radix	$O(n\log n)$	~35	$n\le 10^6$
DC3	$O(n)$	~60	$n\le 10^7$
SA-IS	$O(n)$	~90	the fastest in practice

Write the $O(n{\log }^{2}n)$ version from memory in a contest; keep SA-IS in a template file.

Suffix array vs the alternatives

	Suffix array	Suffix automaton	Suffix tree
Memory	$O(n)$ ints — smallest	$O(n\sigma )$	$O(n\sigma )$
Build	$O(n\log n)$ easy, $O(n)$ hard	$O(n)$, 30 lines	$O(n)$, very hard
Online (append characters)	✘	✔	✔ (Ukkonen)
Lexicographic order	✔ natural	needs work	✔
Count distinct substrings	$O(n)$ after LCP	$O(n)$ directly	$O(n)$
Contest default	when order matters	usually this	rarely

See also: Kasai · Suffix Automaton · SA-IS