Suffix Automaton: Linear-Time Directed Acyclic Word Graphs for Strings

A Suffix Automaton (SAM)—often referred to as a Directed Acyclic Word Graph (DAWG)—is a powerful deterministic finite automaton (DFA) that encodes all substrings of a string $S$ in optimal $O(N)$ time and space.

While a naive suffix trie contains $O(N^2)$ states and Suffix Trees require complex algorithms (like Ukkonen's algorithm) with high constant memory multipliers, a Suffix Automaton compresses all identical substring state transitions using **endpos equivalence classes**, maintaining at most $2N - 1$ states and $3N - 4$ transitions for any string of length $N$.

Theoretical Foundations: endpos Equivalence and Suffix Links

1. The endpos Set

For any non-empty substring $u$ of string $S$, $\text{endpos}(u)$ is defined as the set of all ending index positions where $u$ appears in $S$. Two substrings $u$ and $v$ are **endpos-equivalent** if and only if $\text{endpos}(u) = \text{endpos}(v)$. A single state in a Suffix Automaton corresponds to exactly one unique endpos equivalence class.

2. Structural Lemmas of endpos Classes

• Subset/Disjoint Property: Two endpos sets are either completely disjoint or one is a strict subset of the other.
• Continuous Lengths: Within a single state $v$, all represented substrings are suffixes of the longest string $\text{len}(v)$, and their lengths form a contiguous integer range $[\text{minlen}(v), \text{len}(v)]$.
• Suffix Link (Parent Pointer): The suffix link $\text{link}(v)$ points to the state corresponding to the longest suffix of substrings in $v$ whose endpos set is strictly larger (i.e., appears in additional positions).

Linear-Time Online Construction Algorithm

A Suffix Automaton is built character by character in amortized $O(N)$ time. When extending the automaton with character $c$:

1. Create a new state `cur` with $\text{len}(\text{cur}) = \text{len}(\text{last}) + 1$.
2. Ascend the suffix-link chain starting from `last`. For every state $p$ lacking a transition on $c$, add $\text{next}[p][c] = \text{cur}$.
3. If no state on the link path had a transition on $c$, set $\text{link}(\text{cur}) = 0$ (root) and set $\text{last} = \text{cur}$.
4. If a state $p$ already has transition $q = \text{next}[p][c]$: If $\text{len}(q) == \text{len}(p) + 1$, simply set $\text{link}(\text{cur}) = q$.
5. Otherwise (when $\text{len}(q) > \text{len}(p) + 1$), clone state $q$ into a new state `clone` with $\text{len}(\text{clone}) = \text{len}(p) + 1$, copy $q$'s transitions, redirect $\text{link}(q)$ and $\text{link}(\text{cur})$ to `clone`, and redirect transitions pointing to $q$ along $p$'s link path to `clone`.

C++ Implementation Blueprint

#include <vector>
#include <string>
#include <map>

struct State {
    int len = 0;
    int link = -1;
    std::map<char, int> next;
};

class SuffixAutomaton {
private:
    std::vector<State> st;
    int last = 0;

public:
    SuffixAutomaton(int max_len) {
        st.reserve(2 * max_len);
        st.push_back(State()); // State 0 is the root
    }

    void extend(char c) {
        int cur = st.size();
        st.push_back(State());
        st[cur].len = st[last].len + 1;

        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back(State());
                st[clone].len = st[p].len + 1;
                st[clone].next = st[q].next;
                st[clone].link = st[q].link;

                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }

    bool containsSubstring(const std::string& pattern) const {
        int curr = 0;
        for (char c : pattern) {
            if (!st[curr].next.count(c)) return false;
            curr = st[curr].next.at(c);
        }
        return true;
    }
};

Classic Problems Solved via Suffix Automata

1. Counting Distinct Substrings: Summing $(\text{len}(u) - \text{len}(\text{link}(u)))$ across all states in exact $O(N)$ linear time.
2. Pattern Matching & Occurrence Frequency: Finding whether a pattern of length $M$ exists in $O(M)$ time and calculating total match counts by pushing state frequencies down the suffix link tree.
3. Longest Common Substring (LCS) of Multiple Strings: Traversing the automaton with candidate strings, tracking maximum matching length per transition in $O(\sum |S_i|)$.
4. Lexicographically K-th Substring Query: Performing depth-first state counting on DAG paths to query the $k$-th smallest substring in $O(K)$.
5. Bioinformatics Sequence Analysis: Indexing massive genomic DNA strands (FASTA) to detect repeat units and tandem variations without memory thrashing.