Aho-Corasick
(string/aho_corasick.hpp)

• View this file on GitHub
• Last update: 2026-10-27 07:43:44+09:00
• Include: #include "string/aho_corasick.hpp"

概要

• trie の文字列集合を pattern とするオートマトン。状態は trie のノード番号。

使い方

• aho_corasick<sigma, base>(t): trie t の現在の中身から構築する。
• size(): 状態数を返す。
• next(v, c): 状態 v で文字 c を読んだ次の状態を返す。
• fail(v): 状態 v の文字列の真の接尾辞のうち trie のノードである最長のものを返す。根なら -1。
• count(v): 状態 v の文字列を接尾辞に持つ pattern の個数を返す。
• order(): 状態を深さの昇順に並べた列を返す。

制約

• c は $\text{base} \le c < \text{base} + \sigma$
• $0 \le v <$ size()

計算量

• 構築: $\mathcal{O}(\sigma \cdot \text{size}())$
• その他: $\mathcal{O}(1)$

Depends on

• Trie (string/trie.hpp)

Verified with

• test/unit/aho_corasick.test.cpp
• test/yukicoder/430.test.cpp

Code

#pragma once
#include <array>
#include <cassert>
#include <vector>

#include "string/trie.hpp"
template <int sigma = 26, int base = 'a'> struct aho_corasick {
    explicit aho_corasick(const trie<sigma, base>& t) : _n(t.size()), nxt(_n), fl(_n, -1), cnt(_n) {
        ord.reserve(_n);
        ord.push_back(0);
        for (int i = 0; i < _n; i++) {
            int v = ord[i];
            cnt[v] = t.count(v) + (v == 0 ? 0 : cnt[fl[v]]);
            for (int c = 0; c < sigma; c++) {
                int w = t.next(v, base + c);
                if (w == -1) {
                    nxt[v][c] = v == 0 ? 0 : nxt[fl[v]][c];
                } else {
                    nxt[v][c] = w;
                    fl[w] = v == 0 ? 0 : nxt[fl[v]][c];
                    ord.push_back(w);
                }
            }
        }
        assert(int(ord.size()) == _n);
    }
    int size() const {
        return _n;
    }
    int next(int v, int c) const {
        assert(0 <= v && v < _n);
        int x = c - base;
        assert(0 <= x && x < sigma);
        return nxt[v][x];
    }
    int fail(int v) const {
        assert(0 <= v && v < _n);
        return fl[v];
    }
    int count(int v) const {
        assert(0 <= v && v < _n);
        return cnt[v];
    }
    const std::vector<int>& order() const {
        return ord;
    }

  private:
    int _n;
    std::vector<std::array<int, sigma>> nxt;
    std::vector<int> fl, cnt, ord;
};

#line 2 "string/aho_corasick.hpp"
#include <array>
#include <cassert>
#include <vector>

#line 5 "string/trie.hpp"
template <int sigma = 26, int base = 'a'> struct trie {
    static_assert(sigma >= 1);

public:
    trie() : ch(1), par(1, -1), dep(1, 0), cnt(1, 0), cnt_prefix(1, 0) {
        ch[0].fill(-1);
    }
    int size() const {
        return int(ch.size());
    }
    template <class Seq> int insert(const Seq& s) {
        int v = 0;
        cnt_prefix[v]++;
        for (auto c : s) {
            int x = int(c) - base;
            assert(0 <= x && x < sigma);
            if (ch[v][x] == -1) {
                ch[v][x] = size();
                ch.emplace_back().fill(-1);
                par.push_back(v);
                dep.push_back(dep[v] + 1);
                cnt.push_back(0);
                cnt_prefix.push_back(0);
            }
            v = ch[v][x];
            cnt_prefix[v]++;
        }
        cnt[v]++;
        return v;
    }
    template <class Seq> void erase(const Seq& s) {
        int t = find(s);
        assert(t != -1 && cnt[t] > 0);
        cnt[t]--;
        for (int v = t; v != -1; v = par[v]) cnt_prefix[v]--;
    }
    template <class Seq> int find(const Seq& s) const {
        int v = 0;
        for (auto c : s) {
            v = next(v, int(c));
            if (v == -1) return -1;
        }
        return v;
    }
    int next(int v, int c) const {
        assert(0 <= v && v < size());
        int x = c - base;
        assert(0 <= x && x < sigma);
        return ch[v][x];
    }
    int parent(int v) const {
        assert(0 <= v && v < size());
        return par[v];
    }
    int depth(int v) const {
        assert(0 <= v && v < size());
        return dep[v];
    }
    int count(int v) const {
        assert(0 <= v && v < size());
        return cnt[v];
    }
    int count_prefix(int v) const {
        assert(0 <= v && v < size());
        return cnt_prefix[v];
    }

private:
    std::vector<std::array<int, sigma>> ch;
    std::vector<int> par, dep, cnt, cnt_prefix;
};
#line 7 "string/aho_corasick.hpp"
template <int sigma = 26, int base = 'a'> struct aho_corasick {
    explicit aho_corasick(const trie<sigma, base>& t) : _n(t.size()), nxt(_n), fl(_n, -1), cnt(_n) {
        ord.reserve(_n);
        ord.push_back(0);
        for (int i = 0; i < _n; i++) {
            int v = ord[i];
            cnt[v] = t.count(v) + (v == 0 ? 0 : cnt[fl[v]]);
            for (int c = 0; c < sigma; c++) {
                int w = t.next(v, base + c);
                if (w == -1) {
                    nxt[v][c] = v == 0 ? 0 : nxt[fl[v]][c];
                } else {
                    nxt[v][c] = w;
                    fl[w] = v == 0 ? 0 : nxt[fl[v]][c];
                    ord.push_back(w);
                }
            }
        }
        assert(int(ord.size()) == _n);
    }
    int size() const {
        return _n;
    }
    int next(int v, int c) const {
        assert(0 <= v && v < _n);
        int x = c - base;
        assert(0 <= x && x < sigma);
        return nxt[v][x];
    }
    int fail(int v) const {
        assert(0 <= v && v < _n);
        return fl[v];
    }
    int count(int v) const {
        assert(0 <= v && v < _n);
        return cnt[v];
    }
    const std::vector<int>& order() const {
        return ord;
    }

  private:
    int _n;
    std::vector<std::array<int, sigma>> nxt;
    std::vector<int> fl, cnt, ord;
};

Back to top page