vii. Suffix Automaton

The smallest DFA recognising all substrings of $s$, built online in $O(n)$ with about 30 lines: the best power-to-effort ratio of any string structure. For $n\ge 2$: at most $2n-1$ states (including the initial one) and $3n-4$ transitions (for $n\ge 3$), both tight. A state is an endpos-equivalence class (substrings with the same set of end positions); len[v] is its longest string, the shortest is len[link[v]] + 1, so it represents ${\mathrm{len}}_v-{\mathrm{len}}_{\mathrm{link}(v)}$ distinct substrings. Suffix links form a tree, and the link tree of the automaton of $s$ is the suffix tree of $\mathrm{rev}(s)$. Also: the subsequence automaton.

Question	Method	Cost
is $t$ a substring	run $t$ through the automaton	$O(|t|)$
number / total length of distinct substrings	${\sum }_v({\mathrm{len}}_v-{\mathrm{len}}_{\mathrm{link}(v)})$ / ${\sum }_v\left(\right(\genfrac{}{}{0ex}{}{{\mathrm{len}}_v+1}{2})-(\genfrac{}{}{0ex}{}{{\mathrm{len}}_{\mathrm{link}(v)}+1}{2}\left)\right)$	$O(n)$
occurrences of $t$	cnt of its state (1 per non-clone, summed up the link tree)	$O(|t|)$
first occurrence of $t$	`firstpos[v] -	t
all occurrences	the link subtree of the state (non-clone states)	output size
longest common substring of two strings	run $t$ with fallbacks, track the match length	$O(|t|)$
LCS of $k$ strings	per-state minimum of the best match over all strings, propagated up the link tree	$O(\sum |t_i|)$
$k$-th distinct substring in lexicographic order	descend with path counts	$O(|\text{answer}|\sigma )$
smallest rotation	automaton of $s+s$, take the smallest edge $n$ times	$O(n\sigma )$
LZ factorisation (s-factorisation)	greedy walk with firstpos	$O(n)$
many strings	generalised automaton (reset last, reuse existing transitions)	$O(\sum |s_i|)$

Transitions	memory	access	$n=10^6$
array<int, 26>	$O(26n)$	$O(1)$	208 MB: too much
map<char, int> / sorted vector	$O(n)$	$O(\log \sigma )$	fine

Want	Use
count / enumerate all substrings, LCS, online construction	suffix automaton
lexicographic order of suffixes, $k$-th suffix, minimum memory	suffix array

struct SuffixAutomaton {                                    // lowercase; states 0..sz-1, state 0 = empty string
    vector<array<int, 26>> nxt; vector<int> link, len, firstpos; vector<char> isClone; int last = 0;
    SuffixAutomaton() { newState(0, -1, -1, false); }
    int newState(int L, int lk, int fp, bool clone) { nxt.push_back({}); nxt.back().fill(-1); link.push_back(lk); len.push_back(L); firstpos.push_back(fp); isClone.push_back(clone); return sz(len) - 1; }
    void extend(int c) {
        int cur = newState(len[last] + 1, 0, len[last], false), p = last;
        while (p != -1 && nxt[p][c] == -1) nxt[p][c] = cur, p = link[p];
        if (p != -1) {
            int q = nxt[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int cl = newState(len[p] + 1, link[q], firstpos[q], true); nxt[cl] = nxt[q];
                while (p != -1 && nxt[p][c] == q) nxt[p][c] = cl, p = link[p];
                link[q] = link[cur] = cl;
            }
        }
        last = cur;
    }
    SuffixAutomaton(const string& s) : SuffixAutomaton() { for (char ch : s) extend(ch - 'a'); }
    vector<int> byLen() const {                             // states sorted by len (counting sort)
        int n = sz(len), mx = *max_element(all(len)); vector<int> cnt(mx + 1, 0), ord(n);
        for (int v = 0; v < n; v++) cnt[len[v]]++;
        for (int i = 1; i <= mx; i++) cnt[i] += cnt[i - 1];
        for (int v = n - 1; v >= 0; v--) ord[--cnt[len[v]]] = v;
        return ord;
    }
    vector<ll> occurrences() const {                        // cnt[v] = |endpos(v)|
        vector<ll> cnt(sz(len), 0); for (int v = 1; v < sz(len); v++) cnt[v] = !isClone[v];
        auto ord = byLen(); for (int i = sz(ord) - 1; i > 0; i--) cnt[link[ord[i]]] += cnt[ord[i]];
        return cnt;
    }
    int find(const string& t) const { int v = 0; for (char ch : t) { v = nxt[v][ch - 'a']; if (v == -1) return -1; } return v; }
    ll distinctSubstrings() const { ll r = 0; for (int v = 1; v < sz(len); v++) r += len[v] - len[link[v]]; return r; }
    ll totalLengthDistinct() const { ll r = 0; for (int v = 1; v < sz(len); v++) { ll a = len[v], b = len[link[v]]; r += a * (a + 1) / 2 - b * (b + 1) / 2; } return r; }
    int longestCommonSubstring(const string& t) const {
        int v = 0, l = 0, best = 0;
        for (char ch : t) {
            int c = ch - 'a';
            while (v && nxt[v][c] == -1) v = link[v], l = len[v];
            if (nxt[v][c] != -1) v = nxt[v][c], l++;
            best = max(best, l);
        }
        return best;
    }
    string kthDistinct(ll k) const {                        // 1-indexed, "" if k exceeds the count
        vector<ll> paths(sz(len), 1); auto ord = byLen();   // paths[v] = substrings starting at v (incl. empty)
        for (int i = sz(ord) - 1; i >= 0; i--) { int v = ord[i]; for (int c = 0; c < 26; c++) if (nxt[v][c] != -1) paths[v] += paths[nxt[v][c]]; }
        if (k > paths[0] - 1) return "";
        string res; int v = 0;
        while (k > 0) for (int c = 0; c < 26; c++) { int u = nxt[v][c]; if (u == -1) continue; if (k <= paths[u]) { res += 'a' + c; v = u; k--; break; } k -= paths[u]; }
        return res;
    }
};
 
int lcsMany(const vector<string>& strs) {                  // longest common substring of all strings
    SuffixAutomaton sam(strs[0]); int n = sz(sam.len); auto ord = sam.byLen();
    vector<int> best(sam.len);                              // best[v] = min over strings of the longest match ending in v
    for (int i = 1; i < sz(strs); i++) {
        vector<int> cur(n, 0); int v = 0, l = 0;
        for (char ch : strs[i]) {
            int c = ch - 'a';
            while (v && sam.nxt[v][c] == -1) v = sam.link[v], l = sam.len[v];
            if (sam.nxt[v][c] != -1) v = sam.nxt[v][c], l++;
            cur[v] = max(cur[v], l);
        }
        for (int j = n - 1; j > 0; j--) { int u = ord[j], p = sam.link[u]; cur[p] = max(cur[p], min(cur[u], sam.len[p])); }   // a match in u implies one in its link
        for (int u = 0; u < n; u++) best[u] = min(best[u], cur[u]);
    }
    return *max_element(all(best));
}
string smallestRotation(const string& s) {                 // lexicographically smallest rotation, O(n sigma)
    SuffixAutomaton sam(s + s); string r; int v = 0;
    for (int i = 0; i < sz(s); i++) for (int c = 0; c < 26; c++) if (sam.nxt[v][c] != -1) { r += 'a' + c; v = sam.nxt[v][c]; break; }
    return r;
}
vector<pair<int, int>> lzFactorization(const string& s) {  // (start, length): longest prefix of s[i..] occurring starting before i, else one char
    SuffixAutomaton sam(s); vector<pair<int, int>> res;
    for (int i = 0; i < sz(s);) {
        int v = 0, L = 0;
        while (i + L < sz(s)) {
            int u = sam.nxt[v][s[i + L] - 'a'];
            if (u == -1 || sam.firstpos[u] - L >= i) break;  // first occurrence of s[i, i+L] must start before i
            v = u; L++;
        }
        res.push_back({i, max(L, 1)}); i += max(L, 1);
    }
    return res;
}
 
struct GeneralSAM : SuffixAutomaton {                       // several strings; extend handles existing transitions
    void addString(const string& s) {
        last = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nxt[last][c] != -1) {                       // the extension already exists
                int q = nxt[last][c];
                if (len[q] == len[last] + 1) { last = q; continue; }
                int cl = newState(len[last] + 1, link[q], firstpos[q], true); nxt[cl] = nxt[q];
                for (int p = last; p != -1 && nxt[p][c] == q; p = link[p]) nxt[p][c] = cl;
                link[q] = cl; last = cl; continue;
            }
            extend(c);
        }
    }
};

Proof: construction, sizes and the queries

Endpos classes. For substrings $u$ (shorter) and $w$ with $u$ a suffix of $w$, $\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u)$; two substrings are equivalent iff they have the same endpos set, and each class consists of the suffixes of its longest member with lengths in an interval $({\mathrm{len}}_{\mathrm{link}},\mathrm{len}]$, where the link is the class of the next shorter suffix. Extend. Appending $c$ creates the class of the new full prefix ($\mathrm{len}={\mathrm{len}}_{\text{last}}+1$); walking up the links from last, states without a $c$-transition get one to cur. At the first state $p$ with an existing $c$-transition to $q$: if ${\mathrm{len}}_q={\mathrm{len}}_p+1$, all strings of $q$ are suffixes of the new prefix and $q$ is the link of cur; otherwise $q$ contains longer strings whose endpos does not gain the new position, so $q$ splits: a clone takes the strings of length $\le {\mathrm{len}}_p+1$ (with $q$‘s transitions and link) and the transitions into $q$ from $p$‘s link chain that correspond to short strings are redirected. Sizes: each extend adds at most two states (the new one and a clone), giving $\le 2n-1$, and a counting argument on transitions gives $\le 3n-4$; the total work of the walks is amortised $O(n)$ (Blumer et al.). Distinct substrings: classes partition the substrings. Occurrences: the endpos sets of the link tree are nested, each non-clone state contributes exactly one new end position (its prefix end), so $|\mathrm{endpos}(v)|$ is the number of non-clone states in $v$‘s link subtree. firstpos: the end of the first occurrence, inherited by clones. LCS walk: it maintains the longest suffix of $t[\mathrm{0..}i]$ that is a substring of $s$ (falling back along links shortens it to the longest suffix that can be extended). lcsMany: per state, the best match length ending there is propagated to the link (any match of length $\ge {\mathrm{len}}_{\mathrm{link}}$ in $u$ implies the full ${\mathrm{len}}_{\mathrm{link}}$ in the parent), and the answer is the best per-state minimum. $k$-th substring: paths[v] counts distinct paths from $v$ including the empty one, the automaton being a DAG whose paths from the root are exactly the distinct substrings, enumerated in lexicographic order by trying letters in order. Smallest rotation: rotations are the length-$n$ substrings of $s+s$, and the greedy smallest-letter walk of length $n$ stays inside the automaton because every state on it extends (each rotation can be extended to length $n$). LZ: an occurrence of $s[i..i+L]$ starting before $i$ exists iff the first occurrence starts before $i$, and the property is prefix-closed, so the greedy walk finds the longest factor. All checked against brute force on random strings (also generalised automata against per-string automata).

Subsequence automaton

States are positions $\mathrm{0..}n$; next[i][c] is the smallest $j\ge i$ with $s_j=c$ (or $n$). It is a DAG whose paths from state 0 are exactly the distinct subsequences, which gives “is $t$ a subsequence” in $O(|t|)$, counting distinct subsequences, and the shortest non-subsequence by DP on the same table.

struct SubsequenceAutomaton {
    int n; vector<array<int, 26>> next;
    explicit SubsequenceAutomaton(const string& s) : n(sz(s)), next(sz(s) + 1) {
        next[n].fill(n); for (int i = n - 1; i >= 0; i--) { next[i] = next[i + 1]; next[i][s[i] - 'a'] = i; }
    }
    bool isSubsequence(const string& t) const { int pos = 0; for (char ch : t) { int j = next[pos][ch - 'a']; if (j == n) return false; pos = j + 1; } return true; }
    ll countDistinct(ll mod) const {                        // distinct non-empty subsequences
        vector<ll> dp(n + 2, 0); dp[n] = 1;                 // dp[i] = distinct subsequences (with empty) of s[i, n)
        for (int i = n - 1; i >= 0; i--) { ll tot = 1; for (int c = 0; c < 26; c++) { int j = next[i][c]; if (j < n) tot = (tot + dp[j + 1]) % mod; } dp[i] = tot; }
        return (dp[0] - 1 + mod) % mod;
    }
    string shortestNonSubsequence(int A) const {           // over the first A letters, lexicographically smallest among the shortest
        vector<int> f(n + 2, 0); f[n + 1] = 0;              // f[i] = length of the shortest non-subsequence of s[i, n) (state n + 1 = "past the end")
        for (int i = n; i >= 0; i--) { int best = INT_MAX; for (int c = 0; c < A; c++) { int j = i < n ? next[i][c] : n; best = min(best, 1 + (j == n ? 0 : f[j + 1])); } f[i] = best; }
        string res; int i = 0;
        while (true) {
            for (int c = 0; c < A; c++) {
                int j = i < n ? next[i][c] : n;
                if (1 + (j == n ? 0 : f[j + 1]) == f[i]) { res += 'a' + c; if (j == n) return res; i = j + 1; break; }
            }
        }
    }
};

Proof: subsequence automaton

Greedy leftmost matching is optimal: if $t$ is a subsequence, matching each character at its earliest possible position leaves the longest remaining suffix of $s$ for the rest. So the paths from state 0 (choose letter $c$, jump to next[pos][c] + 1) are in bijection with distinct subsequences (the leftmost embedding is unique), and dp[i] counts paths from position $i$. Shortest non-subsequence: $t$ is not a subsequence of $s[i..)$ iff its first letter $c$ is absent ($t=c$ works, length 1) or $t[\mathrm{1..})$ is not a subsequence of $s[{\mathrm{next}}_i(c)+\mathrm{1..})$; minimising over $c$ in order gives the shortest and lexicographically smallest one. Verified by brute force.

Related notes

• Suffix Array
• Suffix Tree
• String Basics (LZ factorisation, string DP)