Patterns/Part V - Strings, Sequences & Grid/Suffix Automaton

Pattern Reference

Suffix Automaton

"Minimal DFA accepting all suffixes of a string. Count distinct substrings, longest common substring, lexicographically smallest."

Loading...

Deep Dive Tutorial

A SAM state represents an equivalence class of substrings that all end at the same set of positions in the original string. The link tree (suffix links) forms a tree where each state's link points to the longest proper suffix of any string in that state's class. Build online: for each new character, create a new state, extend links, and handle possible cloning when a state needs to be split.

Suffix Automaton construction
class SAM {
    constructor() {
        this.states = [{len: 0, link: -1, next: {}}]; // state 0 = initial
        this.last = 0;
        this.size = 1;
    }

    extend(c) {
        const cur = this.size++;
        this.states.push({len: this.states[this.last].len + 1, link: -1, next: {}});
        let p = this.last;
        while (p !== -1 && !this.states[p].next[c]) {
            this.states[p].next[c] = cur;
            p = this.states[p].link;
        }
        if (p === -1) {
            this.states[cur].link = 0;
        } else {
            const q = this.states[p].next[c];
            if (this.states[p].len + 1 === this.states[q].len) {
                this.states[cur].link = q;
            } else {
                // Clone q
                const clone = this.size++;
                this.states.push({
                    len: this.states[p].len + 1,
                    link: this.states[q].link,
                    next: {...this.states[q].next}
                });
                while (p !== -1 && this.states[p].next[c] === q) {
                    this.states[p].next[c] = clone;
                    p = this.states[p].link;
                }
                this.states[q].link = this.states[cur].link = clone;
            }
        }
        this.last = cur;
    }

    build(s) { for (const c of s) this.extend(c); }

    // Count distinct substrings = sum of (len[v] - len[link[v]]) over all states
    countDistinct() {
        return this.states.slice(1).reduce((s, st) =>
            s + st.len - this.states[st.link].len, 0);
    }
}

Worked Problems

1
Longest Common Substring of Two Strings
Medium
Solve ↗
2
Number of Distinct Substrings
Medium
Solve ↗
3
Shortest Superstring
Hard
Solve ↗
bot
SAM key facts:
- At most 2n states, 3n transitions
- Each state = set of substrings with identical endpos sets
- Suffix link tree = crucial for counting and tree DP
- Build online in O(n) time and space

Common SAM applications:
- Count distinct substrings: Σ(len[v] - len[link[v]])
- LCS of two strings: run second string through SAM of first, track max match
- Count occurrences of each substring: propagate size up suffix link tree
- Lexicographically k-th substring: DFS on DAG structure

vs Suffix Array: SA+LCP is more cache-friendly and often easier. SAM is better when you need to process characters online or need the DAG structure for traversal.
← All Patterns