Suffix Automaton (SAM / DAWG): endpos Equivalence Classes & State Transitions

1. The Four Fundamental Lemmas of $\text{endpos}(t)$

Every property of the Suffix Automaton follows from four elementary facts about $\text{endpos}(t)$:

1. Nested Suffix Inclusion: If $|u| \le |w|$ and $\text{endpos}(u) \cap \text{endpos}(w) \neq \emptyset$, then $u$ MUST be a suffix of $w$, which implies $\text{endpos}(w) \subseteq \text{endpos}(u)$. Thus any two $\text{endpos}$ sets are either completely disjoint or one is a subset of the other!
2. Contiguous Suffix Interval per State: All substrings inside a single equivalence class $q$ are suffixes of the longest substring $W(q)$ in $q$ (of length $\text{len}[q]$), and they consist of all suffixes of $W(q)$ of lengths in the contiguous range $[\text{minlen}[q],\; \text{len}[q]]$.
3. The Suffix Link Tree ($\text{link}[q]$): As you shorten $W(q)$ one character at a time from the left, the set of ending positions stays equal to $\text{endpos}(q)$ down to length $\text{minlen}[q]$, and at length $\text{minlen}[q] - 1$ it strictly expands into a larger $\text{endpos}$ set! That state is defined as $\text{link}[q]$, so: $$\text{minlen}[q] = \text{len}[\text{link}[q]] + 1$$ Because $\text{endpos}$ sets are either disjoint or nested, the links $\text{link}[q]$ form a rooted tree (the Link Tree) with at most $N$ leaves, proving the automaton has at most $2N - 1$ states (and at most $3N - 4$ edges).
4. Instant Substring Count: Since state $q$ represents exactly $\text{len}[q] - \text{len}[\text{link}[q]]$ distinct substrings and states partition all non-empty substrings of $S$, the total number of distinct substrings of $S$ is simply $\sum_{q > 0} (\text{len}[q] - \text{len}[\text{link}[q]])$.

2. Online $O(N)$ Extension & State Cloning

When we append character $c = S[i]$ to the string processed so far (whose full prefix state is $\text{last}$), we create a new state $\text{cur}$ with $\text{len}[\text{cur}] = \text{len}[\text{last}] + 1$, walk up the suffix link chain $p = \text{last}, \text{link}[\text{last}], \dots$ adding transition $\text{next}[p][c] = \text{cur}$ while $\text{next}[p][c]$ is absent, and then handle three cases:

• Case 1 (Reached root with no existing $c$-edge): Set $\text{link}[\text{cur}] = 0$ (the root).
• Case 2 ($q = \text{next}[p][c]$ exists and $\text{len}[q] == \text{len}[p] + 1$): State $q$ contains ONLY suffixes of the new string, so we simply set $\text{link}[\text{cur}] = q$.
• Case 3 ($q = \text{next}[p][c]$ exists and $\text{len}[q] > \text{len}[p] + 1$): State $q$ contains strings longer than $\text{len}[p] + 1$ that do NOT end at index $i$, so their $\text{endpos}$ set has split from the shorter suffixes of length $\le \text{len}[p] + 1$! We clone $q$ into a new state $\text{clone}$ with $\text{len}[\text{clone}] = \text{len}[p] + 1$, copy $q$'s outgoing transitions and suffix link to $\text{clone}$, redirect transitions $\text{next}[p][c] == q$ along $p$'s link chain to $\text{clone}$, and set $\text{link}[q] = \text{link}[\text{cur}] = \text{clone}$.

3. Visual Trace: SAM States & Suffix Links for $S = \texttt{"abcbc"}$

4. Production Implementation: Suffix Automaton + LCS of Two Strings

#include <algorithm>
#include <array>
#include <cstdint>
#include <string_view>
#include <vector>

class SuffixAutomaton {
public:
    struct State {
        std::array<int, 26> next;
        int len = 0;
        int link = -1;
        State() { next.fill(-1); }
    };

    explicit SuffixAutomaton(std::string_view s) {
        st_.reserve(2 * s.size() + 1);
        st_.emplace_back(); // State 0 = root
        for (char ch : s) extend(ch - 'a');
    }

    void extend(int c) {
        int cur = static_cast<int>(st_.size());
        st_.emplace_back();
        st_[cur].len = st_[last_].len + 1;

        int p = last_;
        while (p != -1 && st_[p].next[c] == -1) {
            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 = static_cast<int>(st_.size());
                st_.push_back(st_[q]); // Copies next[] and link
                st_[clone].len = st_[p].len + 1;
                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;
    }

    int64_t count_distinct_substrings() const {
        int64_t total = 0;
        for (size_t u = 1; u < st_.size(); ++u) {
            total += st_[u].len - st_[st_[u].link].len;
        }
        return total;
    }

    // Returns length of Longest Common Substring with T in O(|T|) time
    int longest_common_substring(std::string_view t) const {
        int u = 0, cur_len = 0, best = 0;
        for (char ch : t) {
            int c = ch - 'a';
            while (u != 0 && st_[u].next[c] == -1) {
                u = st_[u].link;
                cur_len = st_[u].len;
            }
            if (st_[u].next[c] != -1) {
                u = st_[u].next[c];
                ++cur_len;
            }
            best = std::max(best, cur_len);
        }
        return best;
    }

private:
    std::vector<State> st_;
    int last_ = 0;
};