Suffix Automaton
(string/suffix_automaton.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

概要

Suffix Automaton を構築する。 文字列中の全ての部分文字列を状態として圧縮表現でき、異なる部分文字列数や各状態の出現回数集計に使える。 この実装は固定文字種向けの配列遷移で、速度を優先している。

計算量

• 構築 : $O(

  S

  )$

• count_distinct_substrings() : $O(

  states

  )$

• substring_occurrences() : $O(

  states

  + max_len)$

文字種数 W はテンプレート引数。各状態の遷移は固定長配列 int next[W] で保持する。

使い方

1. SuffixAutomaton<26, 'a'> sam(s); のように文字種数と開始文字を指定して構築する
2. sam.add(c) で 1 文字ずつ伸ばしてもよい
3. sam.count_distinct_substrings() で異なる部分文字列数を得る
4. sam.substring_occurrences() で各状態に対応する endpos サイズを得る

実装上の補足

• nodes[v].len は状態 v が表す文字列の最大長。
• nodes[v].link は suffix link。
• nodes[v].next は遷移。
• add(c) に渡す文字は start <= c < start + W を満たす前提。
• substring_occurrences() の戻り値は状態ごとの出現回数で、クローン状態は構築時 0 から集約する。

Verified with

• test/yosupo_number_of_substrings_suffix_automaton.test.cpp

Code

template<int W, char start = 'a'>
struct SuffixAutomaton {
    struct Node {
        int link;
        int len;
        int occ;
        int next[W];
        Node(int link = -1, int len = 0, int occ = 0): link(link), len(len), occ(occ) {
            fill(next, next + W, -1);
        }
    };

    vector<Node> nodes;
    int last;

    SuffixAutomaton(): nodes(1), last(0) {}

    template<class Container>
    explicit SuffixAutomaton(const Container &s): SuffixAutomaton() {
        reserve(s.size());
        for (auto &&c : s) add(c);
    }

    void reserve(int n) {
        nodes.reserve(2 * n + 1);
    }

    static int ord(char c) {
        return c - start;
    }

    int add(char c) {
        int k = ord(c);
        int cur = nodes.size();
        nodes.emplace_back(0, nodes[last].len + 1, 1);
        int p = last;
        while (p != -1 && nodes[p].next[k] == -1) {
            nodes[p].next[k] = cur;
            p = nodes[p].link;
        }
        if (p == -1) {
            nodes[cur].link = 0;
            last = cur;
            return cur;
        }
        int q = nodes[p].next[k];
        if (nodes[p].len + 1 == nodes[q].len) {
            nodes[cur].link = q;
            last = cur;
            return cur;
        }
        int clone = nodes.size();
        nodes.push_back(nodes[q]);
        nodes[clone].len = nodes[p].len + 1;
        nodes[clone].occ = 0;
        while (p != -1 && nodes[p].next[k] == q) {
            nodes[p].next[k] = clone;
            p = nodes[p].link;
        }
        nodes[q].link = nodes[cur].link = clone;
        last = cur;
        return cur;
    }

    template<class Container>
    void build(const Container &s) {
        reserve(s.size());
        for (auto &&c : s) add(c);
    }

    long long count_distinct_substrings() const {
        long long res = 0;
        for (int i = 1; i < (int)nodes.size(); ++i) {
            res += nodes[i].len - nodes[nodes[i].link].len;
        }
        return res;
    }

    vector<int> order_by_length() const {
        int max_len = 0;
        for (auto &&node : nodes) max_len = max(max_len, node.len);
        vector<int> cnt(max_len + 1);
        for (auto &&node : nodes) cnt[node.len]++;
        for (int i = 1; i <= max_len; ++i) cnt[i] += cnt[i - 1];
        vector<int> ord(nodes.size());
        for (int i = (int)nodes.size() - 1; i >= 0; --i) {
            ord[--cnt[nodes[i].len]] = i;
        }
        return ord;
    }

    vector<int> substring_occurrences() const {
        auto cnt = nodes;
        auto ord = order_by_length();
        for (int i = (int)ord.size() - 1; i >= 1; --i) {
            int v = ord[i];
            cnt[cnt[v].link].occ += cnt[v].occ;
        }
        vector<int> res(nodes.size());
        for (int i = 0; i < (int)nodes.size(); ++i) res[i] = cnt[i].occ;
        return res;
    }
};
/**
 * @brief Suffix Automaton
 */

#line 1 "string/suffix_automaton.cpp"
template<int W, char start = 'a'>
struct SuffixAutomaton {
    struct Node {
        int link;
        int len;
        int occ;
        int next[W];
        Node(int link = -1, int len = 0, int occ = 0): link(link), len(len), occ(occ) {
            fill(next, next + W, -1);
        }
    };

    vector<Node> nodes;
    int last;

    SuffixAutomaton(): nodes(1), last(0) {}

    template<class Container>
    explicit SuffixAutomaton(const Container &s): SuffixAutomaton() {
        reserve(s.size());
        for (auto &&c : s) add(c);
    }

    void reserve(int n) {
        nodes.reserve(2 * n + 1);
    }

    static int ord(char c) {
        return c - start;
    }

    int add(char c) {
        int k = ord(c);
        int cur = nodes.size();
        nodes.emplace_back(0, nodes[last].len + 1, 1);
        int p = last;
        while (p != -1 && nodes[p].next[k] == -1) {
            nodes[p].next[k] = cur;
            p = nodes[p].link;
        }
        if (p == -1) {
            nodes[cur].link = 0;
            last = cur;
            return cur;
        }
        int q = nodes[p].next[k];
        if (nodes[p].len + 1 == nodes[q].len) {
            nodes[cur].link = q;
            last = cur;
            return cur;
        }
        int clone = nodes.size();
        nodes.push_back(nodes[q]);
        nodes[clone].len = nodes[p].len + 1;
        nodes[clone].occ = 0;
        while (p != -1 && nodes[p].next[k] == q) {
            nodes[p].next[k] = clone;
            p = nodes[p].link;
        }
        nodes[q].link = nodes[cur].link = clone;
        last = cur;
        return cur;
    }

    template<class Container>
    void build(const Container &s) {
        reserve(s.size());
        for (auto &&c : s) add(c);
    }

    long long count_distinct_substrings() const {
        long long res = 0;
        for (int i = 1; i < (int)nodes.size(); ++i) {
            res += nodes[i].len - nodes[nodes[i].link].len;
        }
        return res;
    }

    vector<int> order_by_length() const {
        int max_len = 0;
        for (auto &&node : nodes) max_len = max(max_len, node.len);
        vector<int> cnt(max_len + 1);
        for (auto &&node : nodes) cnt[node.len]++;
        for (int i = 1; i <= max_len; ++i) cnt[i] += cnt[i - 1];
        vector<int> ord(nodes.size());
        for (int i = (int)nodes.size() - 1; i >= 0; --i) {
            ord[--cnt[nodes[i].len]] = i;
        }
        return ord;
    }

    vector<int> substring_occurrences() const {
        auto cnt = nodes;
        auto ord = order_by_length();
        for (int i = (int)ord.size() - 1; i >= 1; --i) {
            int v = ord[i];
            cnt[cnt[v].link].occ += cnt[v].occ;
        }
        vector<int> res(nodes.size());
        for (int i = 0; i < (int)nodes.size(); ++i) res[i] = cnt[i].occ;
        return res;
    }
};
/**
 * @brief Suffix Automaton
 */

Back to top page