vi. Suffix Array and LCP

The sorted order of all suffixes, with the LCP array ($\mathrm{lcp}[i]$ = longest common prefix of the suffixes at ranks $i-1$ and $i$), answers most substring questions with far less memory than a suffix tree. Construction: prefix doubling with radix sort $O(n\log n)$, or SA-IS $O(n)$; LCP by Kasai $O(n)$; LCP of any two suffixes by RMQ.

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

Query	Method	Cost
does / how often $p$ occur	two binary searches on the SA	$O(|p|\log n)$
number of distinct substrings	$\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)-\sum \mathrm{lcp}$	$O(n)$
longest repeated substring	$\max \mathrm{lcp}$	$O(n)$
longest common substring of two strings	concatenate with a separator; max lcp between neighbours from different sides	$O(n)$
longest common substring of $k$ strings	distinct separators, sliding window over the SA covering all $k$ colours, window min-lcp	$O(n\log n)$
LCP of any two suffixes, substring comparison	sparse table over lcp: $O(1)$	$O(n\log n)$ build
$k$-th distinct substring in lexicographic order	walk the SA, each rank contributes $n-s{a}_i-{\mathrm{lcp}}_i$ new substrings	$O(n)$
distinct substrings of many ranges $s[l..r)$	offline sweep + suffix automaton + link-cut tree	$O((n+q){\log }^{2}n)$

The LCP array implicitly encodes the suffix tree: internal nodes are the maximal SA intervals whose minimum lcp equals the node’s string depth, enumerable with a monotonic stack (Monotonic Stack); so SA + LCP has the power of a suffix tree at a fraction of the memory and effort.

Construction	Time	Lines	When
sort suffixes naively	$O(n^2\log n)$	3	$n\le 1000$
prefix doubling (KMR) + sort	$O(n{\log }^{2}n)$	~20	$n\le 10^5$
prefix doubling + radix sort	$O(n\log n)$	~25	$n\le 10^6$, the contest default
DC3 / skew (Kärkkäinen–Sanders)	$O(n)$	~60	$n\le 10^7$
SA-IS (Nong–Zhang–Chan)	$O(n)$	~50	fastest in practice

	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)$ SA-IS	$O(n)$, about 30 lines	$O(n)$ (Ukkonen), hard
online append	no	yes	yes
lexicographic order	natural	needs work	yes
contest default	when order matters	usually	rarely

vector<int> suffixArray(const string& str) {               // prefix doubling with counting sort, O(n log n)
    string s = str + char(0); int n = sz(s), A = 256;      // input must not contain '\0'
    vector<int> p(n), c(n), cnt(max(A, n), 0), pn(n), cn(n);
    for (char ch : s) cnt[(unsigned char)ch]++;
    for (int i = 1; i < A; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) p[--cnt[(unsigned char)s[i]]] = i;
    int cls = 1; c[p[0]] = 0;
    for (int i = 1; i < n; i++) { if (s[p[i]] != s[p[i - 1]]) cls++; c[p[i]] = cls - 1; }
    for (int h = 0; (1 << h) < n; h++) {                   // sort cyclic shifts of length 2^{h+1}
        for (int i = 0; i < n; i++) { pn[i] = p[i] - (1 << h); if (pn[i] < 0) pn[i] += n; }
        fill(cnt.begin(), cnt.begin() + cls, 0);
        for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
        for (int i = 1; i < cls; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0; cls = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]}, prv = {c[p[i - 1]], c[(p[i - 1] + (1 << h)) % n]};
            if (cur != prv) cls++; cn[p[i]] = cls - 1;
        }
        swap(c, cn);
    }
    return vector<int>(p.begin() + 1, p.end());           // drop the sentinel
}
 
vector<int> sais(const vector<int>& s, int K) {             // s ends with a unique 0, values < K; returns SA including the sentinel
    int n = sz(s); if (n == 1) return {0};
    vector<char> S(n, 0); S[n - 1] = 1;                     // S-type flags
    for (int i = n - 2; i >= 0; i--) S[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && S[i + 1]);
    auto isLMS = [&](int i) { return i > 0 && S[i] && !S[i - 1]; };
    vector<int> cnt(K, 0), sa(n), bkt(K); for (int x : s) cnt[x]++;
    auto induce = [&](const vector<int>& lms) {
        fill(all(sa), -1);
        int sum = 0; for (int c = 0; c < K; c++) sum += cnt[c], bkt[c] = sum;          // bucket tails
        for (int i = sz(lms) - 1; i >= 0; i--) sa[--bkt[s[lms[i]]]] = lms[i];
        sum = 0; for (int c = 0; c < K; c++) bkt[c] = sum, sum += cnt[c];              // heads: L-type
        for (int i = 0; i < n; i++) { int j = sa[i] - 1; if (sa[i] > 0 && !S[j]) sa[bkt[s[j]]++] = j; }
        sum = 0; for (int c = 0; c < K; c++) sum += cnt[c], bkt[c] = sum;              // tails: S-type
        for (int i = n - 1; i >= 0; i--) { int j = sa[i] - 1; if (sa[i] > 0 && S[j]) sa[--bkt[s[j]]] = j; }
    };
    vector<int> lms; for (int i = 1; i < n; i++) if (isLMS(i)) lms.push_back(i);
    induce(lms);
    vector<int> name(n, -1); int cur = 0, prev = -1;        // name the LMS substrings in sorted order
    for (int i = 0; i < n; i++) {
        int p = sa[i]; if (!isLMS(p)) continue;
        bool diff = prev == -1;
        for (int d = 0; !diff; d++) {
            if (s[p + d] != s[prev + d] || S[p + d] != S[prev + d]) diff = true;
            else if (d > 0 && isLMS(p + d)) break;          // both substrings ended together: equal
        }
        if (diff) cur++;
        name[p] = cur - 1; prev = p;
    }
    vector<int> red; for (int i : lms) red.push_back(name[i]);
    vector<int> redSa;
    if (cur < sz(lms)) redSa = sais(red, cur);
    else { redSa.assign(sz(lms), 0); for (int i = 0; i < sz(lms); i++) redSa[red[i]] = i; }
    vector<int> sorted(sz(lms)); for (int i = 0; i < sz(lms); i++) sorted[i] = lms[redSa[i]];
    induce(sorted);
    return sa;
}
vector<int> suffixArraySAIS(const string& str) {
    vector<int> s(sz(str) + 1, 0); for (int i = 0; i < sz(str); i++) s[i] = (unsigned char)str[i] + 1;
    auto sa = sais(s, 257); return vector<int>(sa.begin() + 1, sa.end());
}
 
vector<int> kasai(const string& s, const vector<int>& sa) { // lcp[r] = LCP(sa[r-1], sa[r]), lcp[0] = 0
    int n = sz(s); vector<int> rk(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0, k = 0; i < n; i++) {
        if (rk[i] == 0) { k = 0; continue; }
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rk[i]] = k; if (k) k--;
    }
    return lcp;
}
 
struct SuffixStructure {                                    // SA + rank + LCP sparse table
    string s; vector<int> sa, rk, lcp; vector<vector<int>> sp;
    SuffixStructure(const string& str) : s(str), sa(suffixArray(str)), rk(sz(str)) {
        int n = sz(s); for (int i = 0; i < n; i++) rk[sa[i]] = i;
        lcp = kasai(s, sa); sp = {lcp};
        for (int k = 1; (1 << k) <= n; k++) { sp.emplace_back(n); for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]); }
    }
    int lcpOf(int i, int j) const {                         // LCP of suffixes starting at i and j
        int n = sz(s); if (i == j) return n - i;
        int a = min(rk[i], rk[j]) + 1, b = max(rk[i], rk[j]) + 1, k = __lg(b - a);
        return min(sp[k][a], sp[k][b - (1 << k)]);
    }
    int compare(int l1, int r1, int l2, int r2) const {     // s[l1, r1) vs s[l2, r2): -1, 0, 1
        int len1 = r1 - l1, len2 = r2 - l2, k = (len1 && len2) ? min({lcpOf(l1, l2), len1, len2}) : 0;
        if (k == len1 || k == len2) return (len1 > len2) - (len1 < len2);
        return s[l1 + k] < s[l2 + k] ? -1 : 1;
    }
    int countOccurrences(const string& p) const {
        auto lo = partition_point(all(sa), [&](int i) { return s.compare(i, sz(p), p) < 0; });
        auto hi = partition_point(all(sa), [&](int i) { return s.compare(i, sz(p), p) <= 0; });
        return hi - lo;
    }
    ll distinctSubstrings() const { ll n = sz(s), t = n * (n + 1) / 2; for (int x : lcp) t -= x; return t; }
    string kthDistinct(ll k) const {                        // 1-indexed k-th distinct substring, "" if k too large
        for (int r = 0; r < sz(s); r++) { ll fresh = sz(s) - sa[r] - lcp[r]; if (k <= fresh) return s.substr(sa[r], lcp[r] + k); k -= fresh; }
        return "";
    }
};
 
int longestCommonSubstring(const vector<string>& strs) {   // over all k strings; O(n log n) via SA on ints
    int k = sz(strs); vector<int> s, owner;
    for (int i = 0; i < k; i++) { for (char c : strs[i]) s.push_back((unsigned char)c + k + 1), owner.push_back(i); s.push_back(i + 1); owner.push_back(-1); }
    s.push_back(0); owner.push_back(-1);                    // separators 1..k are distinct and smaller than letters
    int n = sz(s); vector<int> sa = sais(s, 256 + k + 2), rk(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0, h = 0; i < n; i++) {                    // Kasai on ints; separators never match
        if (rk[i] == 0) { h = 0; continue; }
        int j = sa[rk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h] && s[i + h] > k) h++;
        lcp[rk[i]] = h; if (h) h--;
    }
    if (k == 1) return sz(strs[0]);
    vector<int> have(k, 0); int distinct = 0, best = 0; deque<int> dq;   // window [l, r] of ranks, min lcp over (l, r]
    for (int l = 0, r = 0; r < n; r++) {
        int o = owner[sa[r]]; if (o >= 0 && have[o]++ == 0) distinct++;
        while (!dq.empty() && lcp[dq.back()] >= lcp[r]) dq.pop_back(); dq.push_back(r);
        while (distinct == k) {
            while (!dq.empty() && dq.front() <= l) dq.pop_front();
            if (!dq.empty() && l < r) best = max(best, lcp[dq.front()]);
            int ol = owner[sa[l]]; if (ol >= 0 && --have[ol] == 0) distinct--;
            l++;
        }
    }
    return best;
}

Proof: prefix doubling, Kasai, and the applications

Doubling. With the sentinel the suffixes are the cyclic shifts and the sentinel makes cyclic order equal suffix order. If $c$ ranks the cyclic substrings of length $2^h$, the substring of length $2^{h+1}$ at $i$ is the pair $(c_i,c_{i+2^h})$; the sort by second key is obtained for free by shifting the previous order ($p_i-2^h$), and a stable counting sort by the first key completes the pair sort. After $\lceil {\log }_{2}n\rceil$ rounds the lengths exceed $n$ and the order is the suffix order. Kasai. If suffix $i$ has lcp $k>0$ with its predecessor $j$ in SA order, then suffix $i+1$ shares $k-1$ characters with $j+1$, and $j+1$ precedes $i+1$, so the predecessor of $i+1$ shares at least $k-1$ (everything between two suffixes in sorted order shares their common prefix). Starting each comparison at $k-1$, $k$ decreases at most $n$ times overall, so the total work is $O(n)$. LCP of two suffixes = minimum of lcp strictly between their ranks (the same “sorted order” fact). Distinct substrings: each substring is a prefix of the suffixes in a contiguous SA interval; counting prefixes of each suffix that are not prefixes of its predecessor ($n-s{a}_r-{\mathrm{lcp}}_r$) counts each distinct substring once, in lexicographic order, which also gives the $k$-th one. Occurrences: suffixes starting with $p$ form a contiguous SA block found by two binary searches. Common substring of $k$ strings: a common substring of length $L$ is a common prefix of suffixes from all $k$ strings, i.e. of some SA window containing all colours whose internal lcp minimum is $\ge L$; the smallest windows ending at each rank suffice, maintained by two pointers and a monotonic deque. Distinct separators prevent matches across string boundaries. All verified against brute force on random strings.

Proof: SA-IS

Call suffix $i$ S-type if it is smaller than suffix $i+1$ and L-type if larger (equal first characters inherit the type of $i+1$); LMS positions are S-type with an L-type left neighbour. Bucket fact: within a bucket of equal first characters $c$, all L-type suffixes precede all S-type ones. Since types are inherited across runs of equal characters, an L-suffix is $c^{a}e\cdots$ with $e<c$ (or the sentinel) and an S-suffix is $c^{b}f\cdots$ with $f>c$; at the first position where they differ the L-suffix shows $e$ (if $a\le b$) against $c$ or $f$, or the S-suffix shows $f$ against $c$ (if $a>b$), and in both cases the L-suffix is smaller. Induced sorting: if the LMS suffixes are placed at the bucket tails in their correct relative order, the left-to-right pass places every L-suffix $j$ right after its successor $j+1$ has been placed, at the current head of its bucket; since L-suffixes in a bucket are ordered by their successors, which are scanned in sorted order, they come out sorted. Symmetrically the right-to-left pass sorts the S-suffixes. Reduction: with LMS positions in arbitrary order the passes sort the LMS substrings (from one LMS position to the next, inclusive) correctly, so they can be named by rank; the suffix order of the reduced string of names equals the order of the LMS suffixes, computed recursively (or directly if all names are distinct). The reduced string has length $\le n/2$ (no two adjacent LMS positions), so $T(n)=T(n/2)+O(n)=O(n)$. The sentinel is the unique smallest LMS substring, which keeps the precondition in the recursion. Verified against the doubling algorithm on random strings over alphabets of size 1 to 26 and lengths up to $10^5$.

Karp–Miller–Rosenberg naming

The doubling table ${\mathrm{id}}_k[i]$ = class of $s[i..i+2^k)$ gives deterministic $O(1)$ equality of equal-length substrings ($s[i..i+L)=s[j..j+L)$ iff the two overlapping halves of length $2^{\lfloor \log L\rfloor }$ agree), an exact alternative to hashing at $O(n\log n)$ memory; with binary search it gives $O(\log n)$ LCE and is the basis of tandem-repeat and periodicity queries. DC3 / skew: sort the suffixes at positions $\not\equiv 0(\mathrm{mod}3)$ recursively (names of character triples, a string of length $2n/3$), sort the $\equiv 0$ suffixes by (character, rank of the next suffix), and merge with $O(1)$ comparisons because $\{1,2\}$ is a difference cover mod 3: $T(n)=T(2n/3)+O(n)$. Difference covers mod $v$ also give sublinear-space LCE.

struct KMR {                                                // id[k][i] = class of s[i, i + 2^k)
    vector<vector<int>> id;
    KMR(const string& s) {
        int n = sz(s), LOG = 1; while ((1 << LOG) < n) LOG++;
        id.assign(LOG + 1, vector<int>(n));
        for (int i = 0; i < n; i++) id[0][i] = (unsigned char)s[i];
        for (int k = 0; k < LOG; k++) {
            int len = 1 << k; vector<pair<pair<int, int>, int>> a(n);
            for (int i = 0; i < n; i++) a[i] = {{id[k][i], i + len < n ? id[k][i + len] : -1}, i};
            sort(all(a)); int c = 0;
            for (int i = 0; i < n; i++) { if (i && a[i].first != a[i - 1].first) c++; id[k + 1][a[i].second] = c; }
        }
    }
    bool equal(int i, int j, int L) const {                 // s[i, i+L) == s[j, j+L), L >= 1
        int k = __lg(L);
        return id[k][i] == id[k][j] && id[k][i + L - (1 << k)] == id[k][j + L - (1 << k)];
    }
};

Distinct substrings of many ranges

For queries $[l,r)$, count distinct non-empty substrings of $s[l..r)$, offline. Sweep $r$: charge each distinct substring of $s[\mathrm{0..}r)$ to the start of its last occurrence; the answer is the sum of charges at starts $\ge l$ (Fenwick tree with range add / range sum). Appending $s[r-1]$ makes every suffix of $s[\mathrm{0..}r)$ end at $r-1$: these are the strings on the suffix-link path of the prefix state in the suffix automaton. A link-cut-tree access recolours that path with $r-1$; each preferred path met had a single previous end $p$ and a contiguous length range $[lo,hi]$, so starts $p-hi+\mathrm{1..}p-lo+1$ lose their charge, and the new range gains it. Amortised $O(\log n)$ pieces per access: $O((n+q){\log }^{2}n)$.

struct DistinctSubstringsInRange {                          // lowercase s; queries [l, r)
    struct SAM {
        vector<array<int, 26>> next; vector<int> link, len; int last = 0;
        SAM() : next(1), link(1, -1), len(1, 0) { next[0].fill(-1); }
        int add(int c) {
            int cur = sz(next); next.push_back({}), next[cur].fill(-1), link.push_back(0), len.push_back(len[last] + 1);
            int p = last;
            while (p != -1 && next[p][c] == -1) next[p][c] = cur, p = link[p];
            if (p != -1) {
                int q = next[p][c];
                if (len[p] + 1 == len[q]) link[cur] = q;
                else {
                    int clone = sz(next); next.push_back(next[q]), link.push_back(link[q]), len.push_back(len[p] + 1);
                    while (p != -1 && next[p][c] == q) next[p][c] = clone, p = link[p];
                    link[q] = link[cur] = clone;
                }
            }
            return last = cur;
        }
    };
    vector<int> ch0, ch1, fa, col, tag, lo, mn, len; vector<ll> b1, b2; int n; vector<ll> answers;
    void addPrefix(vector<ll>& b, int i, ll v) { for (i++; i <= n; i += i & -i) b[i] += v; }
    void rangeAdd(int l, int r, ll v) { addPrefix(b1, l, v), addPrefix(b1, r + 1, -v); addPrefix(b2, l, v * l), addPrefix(b2, r + 1, -v * (r + 1)); }
    ll prefixSum(int i) { ll s1 = 0, s2 = 0; for (int j = i; j > 0; j -= j & -j) s1 += b1[j], s2 += b2[j]; return s1 * i - s2; }
    bool isRoot(int x) { return !fa[x] || (ch0[fa[x]] != x && ch1[fa[x]] != x); }
    void apply(int x, int c) { if (x) col[x] = tag[x] = c; }
    void push(int x) { if (tag[x] != -2) apply(ch0[x], tag[x]), apply(ch1[x], tag[x]), tag[x] = -2; }
    void pull(int x) { mn[x] = min({lo[x], mn[ch0[x]], mn[ch1[x]]}); }
    void rotate(int x) {
        int p = fa[x], g = fa[p]; bool right = ch1[p] == x;
        if (!isRoot(p)) (ch0[g] == p ? ch0[g] : ch1[g]) = x;
        fa[x] = g; int b = right ? ch0[x] : ch1[x];
        (right ? ch1[p] : ch0[p]) = b; if (b) fa[b] = p;
        (right ? ch0[x] : ch1[x]) = p; fa[p] = x; pull(p), pull(x);
    }
    void splay(int x) {
        vector<int> path = {x}; for (int y = x; !isRoot(y); y = fa[y]) path.push_back(fa[y]);
        for (int i = sz(path) - 1; i >= 0; i--) push(path[i]);
        while (!isRoot(x)) { int p = fa[x], g = fa[p]; if (!isRoot(p)) rotate((ch0[g] == p) == (ch0[p] == x) ? p : x); rotate(x); }
    }
    void access(int x, int r) {                             // recolour root..x with end position r
        for (int y = x, last = 0; y; last = y, y = fa[y]) {
            splay(y);
            if (col[y] >= 0) { int a = min(mn[ch0[y]], lo[y]), b = len[y], p = col[y]; rangeAdd(p - b + 1, p - a + 1, -1); }
            ch1[y] = last; pull(y);
        }
        splay(x); apply(x, r); rangeAdd(r - len[x] + 1, r, 1);
    }
    DistinctSubstringsInRange(const string& s, const vector<pair<int, int>>& qs) : n(sz(s)) {
        SAM sam; vector<int> prefixState(n);
        for (int i = 0; i < n; i++) prefixState[i] = sam.add(s[i] - 'a');
        int m = sz(sam.len);
        ch0.assign(m, 0), ch1.assign(m, 0), fa.assign(m, 0), col.assign(m, -1), tag.assign(m, -2);
        lo.assign(m, INT_MAX), mn.assign(m, INT_MAX), len = sam.len;
        for (int v = 1; v < m; v++) fa[v] = sam.link[v], lo[v] = mn[v] = sam.len[sam.link[v]] + 1;
        b1.assign(n + 2, 0), b2.assign(n + 2, 0);
        vector<vector<int>> byEnd(n + 1); for (int i = 0; i < sz(qs); i++) byEnd[qs[i].second].push_back(i);
        answers.assign(sz(qs), 0);
        for (int r = 0; r <= n; r++) {
            if (r > 0) access(prefixState[r - 1], r - 1);
            for (int i : byEnd[r]) answers[i] = prefixSum(n) - prefixSum(qs[i].first);
        }
    }
};

Proof: the charging invariant for range distinct substrings

Invariant after processing prefix $s[\mathrm{0..}r)$: for every start $x$, the Fenwick value at $x$ equals the number of distinct substrings of $s[\mathrm{0..}r)$ whose last occurrence starts at $x$. Then the distinct substrings of $s[l..r)$ are exactly those whose last occurrence (within $s[\mathrm{0..}r)$) starts at $\ge l$: a substring occurring in $s[l..r)$ has its last occurrence there, and conversely. When $s[r-1]$ is appended, the substrings whose last occurrence changes are exactly the suffixes of $s[\mathrm{0..}r)$ (their last end becomes $r-1$). In the suffix automaton these are the strings of the states on the suffix-link path from the prefix state to the root, each state covering lengths $(\mathrm{len}(\mathrm{link}),\mathrm{len}]$. A preferred path of the link-cut tree stores one common colour (previous last end $p$) because whenever a path was accessed all of it was recoloured together; for that piece, the lengths form the contiguous range $[\min lo,\mathrm{len}(y)]$ and their old starts $p-\text{length}+1$ form a contiguous range, which loses one charge each; finally all suffixes get the new start range $[r-\mathrm{len}(x),r-1]$. Link-cut amortisation gives $O(\log n)$ pieces per access. Verified against brute-force set counting for all ranges of random strings.

Related notes

• Suffix Automaton
• Suffix Tree
• Burrows–Wheeler (BWT from the SA)