AntInLoop

Suffix Automaton (SAM)

A Suffix Automaton is the minimal deterministic finite automaton accepting all suffixes of a string, built online in linear O(n) time with at most 2n - 1 states to solve distinct substring, occurrence count, and LCS queries.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Suffix Automaton (SAM)

A Suffix Automaton (SAM) of a string $S$ (length $n$) is the smallest deterministic finite automaton (DFA) that accepts every suffix of $S$—meaning every path starting from the initial state 0 spells out a unique substring of $S$! Remarkably, it has at most $2n - 1$ states and $3n - 4$ transitions, and can be constructed online (one character at a time) in $O(n)$ time!

At a Glance

| Property | Value |

| :--- | :--- |

| Build Time | $O(n)$ (online, character by character) |

| Max States / Transitions | $\le 2n - 1$ states, $\le 3n - 4$ transitions |

| Auxiliary Space | $O(n \cdot |\Sigma|)$ (or $O(n)$ with std::map transitions) |

| Best Used When | Counting distinct substrings online, $k$-th lexicographical substring, longest common substring in $O(n + m)$, occurrence counts |

---

How It Works

Each state u represents an equivalence class (endpos-class) of substrings that always end at the exact same set of positions in $S$. It stores:

  • len[u]: length of the longest substring in this class.
  • link[u]: suffix link pointing to the state of the longest suffix of u that belongs to a strictly larger endpos set.
  • next[u][c]: transition on character c.
  • Key Formula: State u represents exactly len[u] - len[link[u]] distinct substrings!

When extending the SAM by character c (extend(c)):

1. Create new state cur with len[cur] = len[last] + 1.

2. Walk p = last upward via link[p] while p != -1 and next[p][c] is absent, setting next[p][c] = cur.

3. If p == -1, set link[cur] = 0.

4. Otherwise let q = next[p][c]. If len[p] + 1 == len[q], set link[cur] = q.

5. Else clone state q into a new state clone with len[clone] = len[p] + 1, redirect p's ancestors pointing to q toward clone, and set link[q] = link[cur] = clone.

6. Update last = cur.

---

Complexity & Key Insights

  • Why len[u] - len[link[u]] Counts Distinct Substrings Online: Every time extend(c) finishes, the number of brand-new distinct substrings introduced by character c is simply len[cur] - len[link[cur]]!
  • Occurrence Count of Any Substring: Mark occ[cur] = 1 for every non-cloned state created in extend(c), then propagate occ[link[u]] += occ[u] in decreasing order of len[u]! Walking any pattern P from state 0 lands on state u whose occ[u] is the exact frequency of P in $S$ in $O(|P|)$ time!

---

Practice Problems

Easy

1. Count Distinct Substrings in $O(n)$

Compute the exact number of distinct non-empty substrings of s in linear time using a Suffix Automaton.

Approach: Build SAM with extend(c) and sum len[u] - len[link[u]] over all states u >= 1. Time: $O(n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <array>
#include <iostream>
#include <string>
#include <vector>

struct SAM {
    struct State {
        std::array<int, 26> next{};
        int link = -1, len = 0;
        State() { next.fill(-1); }
    };
    std::vector<State> st{1};
    int last = 0;

    void extend(char ch) {
        int c = ch - 'a';
        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]);
                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;
    }

    long long countDistinctSubstrings() const {
        long long total = 0;
        for (size_t i = 1; i < st.size(); ++i) {
            total += st[i].len - st[st[i].link].len;
        }
        return total;
    }
};

int main() {
    SAM sam;
    for (char c : std::string("banana")) sam.extend(c);
    std::cout << sam.countDistinctSubstrings() << "\n"; // 15
    return 0;
}

</details>

2. Substring Existence Check in $O(|P|)$

Preprocess text T in $O(|T|)$ and answer whether any query pattern P is a substring of T in $O(|P|)$ time.

Approach: Walk transitions u = st[u].next[c - 'a'] from u = 0; return false if any transition is -1. Time: $O(|P|)$ per query.

<details>

<summary>Show C++ Solution</summary>

#include <array>
#include <iostream>
#include <string>
#include <vector>

struct SAM {
    struct State {
        std::array<int, 26> next{};
        int link = -1, len = 0;
        State() { next.fill(-1); }
    };
    std::vector<State> st{1};
    int last = 0;
    void extend(char ch) {
        int c = ch - 'a', 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]); 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;
    }
    bool contains(const std::string& p) const {
        int u = 0;
        for (char c : p) {
            u = st[u].next[c - 'a'];
            if (u == -1) return false;
        }
        return true;
    }
};

int main() {
    SAM sam;
    for (char c : std::string("abracadabra")) sam.extend(c);
    std::cout << std::boolalpha << sam.contains("cadab") << " " << sam.contains("xyz") << "\n";
    return 0;
}

</details>

---

Intermediate

3. Longest Common Substring of Two Strings in $O(n + m)$

Find the longest substring common to both a and b in strictly linear $O(n + m)$ time!

Approach: Build SAM on a, then stream b maintaining current state u and match length l. If next[u][c] exists, advance u and ++l; otherwise follow suffix links u = link[u] until a transition on c exists (resetting l = len[u] + 1). Track maximum l! Time: $O(n + m)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>

struct SAM {
    struct State {
        std::array<int, 26> next{};
        int link = -1, len = 0;
        State() { next.fill(-1); }
    };
    std::vector<State> st{1};
    int last = 0;
    void extend(char ch) {
        int c = ch - 'a', 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]); 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;
    }
};

std::string longestCommonSubstringSAM(const std::string& a, const std::string& b) {
    SAM sam;
    for (char c : a) sam.extend(c);

    int u = 0, curLen = 0, bestLen = 0, bestEnd = 0;
    for (int i = 0; i < static_cast<int>(b.size()); ++i) {
        int c = b[i] - 'a';
        while (u != 0 && sam.st[u].next[c] == -1) {
            u = sam.st[u].link;
            curLen = sam.st[u].len;
        }
        if (sam.st[u].next[c] != -1) {
            u = sam.st[u].next[c];
            ++curLen;
        }
        if (curLen > bestLen) { bestLen = curLen; bestEnd = i; }
    }
    return bestLen == 0 ? "" : b.substr(bestEnd - bestLen + 1, bestLen);
}

int main() {
    std::cout << longestCommonSubstringSAM("ababc", "babca") << "\n"; // babc
    return 0;
}

</details>

4. Count Occurrences of Any Query Pattern in $O(|P|)$

Preprocess text T in $O(|T|)$ and answer how many times any pattern P appears in T in $O(|P|)$ time.

Approach: Set occ[cur] = 1 on real states (and 0 on clones), sort states by len descending, and propagate occ[link[u]] += occ[u]. Then walk P from 0 and return occ[u]. Time: $O(|T|)$ build, $O(|P|)$ query.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct SAMCount {
    struct State {
        std::array<int, 26> next{};
        int link = -1, len = 0;
        long long occ = 0;
        State() { next.fill(-1); }
    };
    std::vector<State> st{1};
    int last = 0;

    void extend(char ch) {
        int c = ch - 'a', cur = static_cast<int>(st.size());
        st.emplace_back(); st[cur].len = st[last].len + 1; st[cur].occ = 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]); st[clone].len = st[p].len + 1; st[clone].occ = 0;
                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;
    }

    void finalizeCounts() {
        std::vector<int> order(st.size());
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int a, int b) { return st[a].len > st[b].len; });
        for (int u : order) {
            if (st[u].link != -1) st[st[u].link].occ += st[u].occ;
        }
    }

    long long count(const std::string& p) const {
        int u = 0;
        for (char c : p) {
            u = st[u].next[c - 'a'];
            if (u == -1) return 0;
        }
        return st[u].occ;
    }
};

int main() {
    SAMCount sam;
    for (char c : std::string("banana")) sam.extend(c);
    sam.finalizeCounts();
    std::cout << sam.count("ana") << " " << sam.count("a") << " " << sam.count("z") << "\n"; // 2 3 0
    return 0;
}

</details>

---

Hard

5. $k$-th Lexicographical Distinct Substring (SPOJ SUBLEX)

Find the $k$-th smallest distinct non-empty substring of s (1-indexed) in $O(|ans| \cdot |\Sigma|)$ per query after $O(n)$ preprocessing.

Approach: On the SAM DAG, compute paths[u] = number of distinct non-empty substrings reachable from u (1 + sum(paths[next[u][c]]) in reverse topological order of len). To find the $k$-th substring, start at u = 0 and greedily pick the smallest character c whose paths[next[u][c]] >= k (otherwise subtract paths[next[u][c]] from k)!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct SAMKth {
    struct State {
        std::array<int, 26> next{};
        int link = -1, len = 0;
        State() { next.fill(-1); }
    };
    std::vector<State> st{1};
    std::vector<long long> paths;
    int last = 0;

    void extend(char ch) {
        int c = ch - 'a', 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]); 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;
    }

    void buildPaths() {
        std::vector<int> order(st.size());
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int a, int b) { return st[a].len > st[b].len; });
        paths.assign(st.size(), 1);
        for (int u : order) {
            for (int c = 0; c < 26; ++c) {
                if (st[u].next[c] != -1) paths[u] += paths[st[u].next[c]];
            }
        }
    }

    std::string kthSubstring(long long k) const {
        std::string res;
        int u = 0;
        while (k > 0) {
            for (int c = 0; c < 26; ++c) {
                int v = st[u].next[c];
                if (v == -1) continue;
                if (k <= paths[v]) {
                    res.push_back(static_cast<char>('a' + c));
                    --k; // count substring ending right here
                    u = v;
                    break;
                }
                k -= paths[v];
            }
        }
        return res;
    }
};

int main() {
    SAMKth sam;
    for (char c : std::string("abac")) sam.extend(c);
    sam.buildPaths();
    // Sorted distinct substrings of "abac": a, ab, aba, abac, ac, b, ba, bac, c
    std::cout << sam.kthSubstring(1) << " " << sam.kthSubstring(4) << " " << sam.kthSubstring(9) << "\n";
    return 0;
}

</details>

---

Related Algorithms