Suffix Arrays, LCP, and Suffix Structures

Suffix ordering, construction overview, LCP array, repeated-substring queries, distinct-substring counting, pattern search, suffix automaton, and suffix tree concepts.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Every substring is a prefix of some suffix. Adjacent sorted suffixes share lcp[i] prefixes, so the number of distinct substrings is n(n+1)/2 − Σ lcp. A pattern search binary-searches the suffix array in O(m log n). Faster constructions exist (SA-IS in O(n)); a suffix automaton recognises all substrings with at most 2n − 1 states and is built online in O(n); a suffix tree is the compressed trie of all suffixes.

#include <bits/stdc++.h>
using namespace std;

vector<int> suffixArray(const string& s) {                     // prefix doubling, O(n log^2 n)
    int n = (int)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] = (unsigned char)s[i];
    for (int k = 1;; k <<= 1) {
        auto key = [&](int i) { return make_pair(rank[i], i + k < n ? rank[i + k] : -1); };   // sort by first 2k chars
        sort(sa.begin(), sa.end(), [&](int a, int b) { return key(a) < key(b); });
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i) tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]));
        rank = tmp;
        if (rank[sa[n - 1]] == n - 1) break;                   // all ranks distinct
    }
    return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) {  // Kasai, O(n)
    int n = (int)s.size(); vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    for (int i = 0, h = 0; i < n; ++i) {
        if (rank[i] == 0) { h = 0; continue; }
        int j = sa[rank[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[rank[i]] = h;           
…

i  sa  lcp  suffix
0  5   0    a
1  3   1    ana
2  1   3    anana
3  0   0    banana
4  4   0    na
5  2   2    nana
distinct substrings: 15 (brute force 15)
longest repeated substring: "ana"
suffix arrays match direct sorting on 300 random strings

Quiz

? How many distinct substrings does "banana" have, per the run?
+ 15 :: 21 total substrings minus Σ lcp = 6.
- 21 :: That counts duplicates.
- 6 :: That is the number of suffixes.
- 10 :: No.

? What does lcp[i] store?
+ The length of the longest common prefix of the i-th and (i−1)-th suffixes in sorted order :: Kasai computes it in O(n).
- The length of the i-th suffix :: No.
- A rank :: No.
- The number of occurrences :: No.

? Why does Kasai's algorithm decrement h by only one between steps?
+ Removing the first character of a suffix can shorten its LCP with its neighbour by at most one :: Gives O(n) total.
- To avoid overflow :: No.
- It is arbitrary :: It is the key to linearity.
- Because the alphabet is small :: Independent of the alphabet.