Suffix Automaton

The smallest deterministic automaton recognising all substrings of a string. Built online in $O (n)$ , in about 30 lines — the best power-to-effort ratio of any string structure.

The construction

struct SAM {
    struct State { int len = 0, link = -1; map<char,int> nxt; };
    vector<State> st;
    int last;
 
    SAM() { st.push_back({}); last = 0; }
 
    void extend(char c) {
        int cur = st.size(); st.push_back({});
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p != -1 && !st[p].nxt.count(c)) { st[p].nxt[c] = cur; p = st[p].link; }
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].nxt[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;
            else {
                int clone = st.size(); st.push_back(st[q]);      // copy transitions and link
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].nxt[c] == q) { st[p].nxt[c] = clone; p = st[p].link; }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }
};

Size: at most $2 n - 1$ states and $3 n - 4$ transitions. Both bounds are tight.

What the pieces mean

A state represents an equivalence class of substrings that occur at exactly the same set of end positions (its endpos set).
len[v] is the longest string in that class. The shortest is len[link[v]] + 1, so the state represents exactly $len [v] - len [link [v]]$ distinct substrings.
link[v] (the suffix link) points to the state of the longest proper suffix in a different class. The links form a tree — the link tree.

The link tree of the suffix automaton of $s$ is the suffix tree of $reverse (s)$ .

That identity is why the automaton answers suffix-tree questions.

What it answers

Question	Method	Cost
Is $t$ a substring?	run $t$ through the automaton	$O (∣ t ∣)$
Number of distinct substrings	$\sum_{v} (len [v] - len [link [v]])$	$O (n)$
Total length of all distinct substrings	similar sum	$O (n)$
Number of occurrences of $t$	`cnt` of the state, propagated up the link tree	$O (∣ t ∣)$
First occurrence position of $t$	`firstpos` of the state	$O (∣ t ∣)$
All occurrence positions	traverse the link subtree	$O (output)$
Longest common substring of two strings	run $t$ through the SAM of $s$ , tracking the current match length	$O (∣ t ∣)$
LCS of $k$ strings	run each through, take the per-state minimum	$O (\sum ∣ t_{i} ∣)$
$k$ -th lexicographic substring	descend using path counts	$O (∣ an s w er ∣ σ)$
Smallest cyclic rotation	build the SAM of $s + s$ , greedily take the smallest edge $n$ times	$O (nσ)$

Occurrence counts

// cnt[v] = 1 for every non-clone state created by extend(), 0 for clones
// then propagate up the link tree in decreasing order of len
vector<int> order = sortStatesByLen();
for (int i = order.size() - 1; i > 0; i--) cnt[st[order[i]].link] += cnt[order[i]];

Sorting by len is a counting sort — the link tree is naturally ordered by length.

Longest common substring

int v = 0, l = 0, best = 0;
for (char c : t) {
    while (v && !st[v].nxt.count(c)) { v = st[v].link; l = st[v].len; }  // fall back
    if (st[v].nxt.count(c)) { v = st[v].nxt[c]; l++; }
    best = max(best, l);
}

Six lines, $O (∣ t ∣)$ , and it is the standard solution to a problem that looks like it needs a suffix tree.

Transitions: `map` vs array

	`map<char,int>`	`array<int,26>`
Memory	$O (n)$ total	$O (26 n)$
Access	$O (lo g σ)$	$O (1)$
$n = 1 0^{6}$	fine	208 MB — too much

Use array for small $n$ and a map (or a sorted vector) for large $n$ .

Generalised suffix automaton

To handle several strings, feed them all in, resetting last = 0 between them, and check for existing transitions before creating a state. Slightly fiddly; the alternative is to concatenate with distinct separators.