Aho-Corasick
(string/aho-corasick.hpp)

View this file on GitHub
Last update: 2026-08-26 13:48:57+09:00
Include: #include "string/aho-corasick.hpp"

複数のパターン文字列を Aho-Corasick automaton で検索する．

パターン文字列から構築した Trie に failure link と遷移を追加した automaton である．検索文字列を先頭から 1 文字ずつ automaton に通すことで，すべてのパターンを同時に検索する．

AhoCorasick<char_size, char_start> として使う．扱える文字は char_start 以上 char_start + char_size 未満とし，空のパターン文字列は扱わない．すべてのパターンを追加してから build() を 1 回呼び，以降はパターンを追加しないことを要求する．

add(s)：パターン s を追加し，追加順の ID を返す．
size()：追加したパターン数を返す．
node_size()：automaton のノード数を返す．
get_root()：root の index を返す．
accept(v)：ノード v で一致するパターン ID の列を返す．
build()：failure link と遷移を構築する．
move(v, c)：ノード v から文字 c で遷移した先を返す．
match(s)：s における各パターンの出現回数を unordered_map<ID, count> で返す．出現しない ID は含まない．
match_any(s)：s における全パターンの出現回数の総和を返す．

アルゴリズム

Trie の各ノードを，root からそのノードまでの文字列と同一視する．ノード $v$ の failure link を，$v$ 自身を除く suffix のうち Trie に存在する最長のものに対応するノードへの辺とする．

failure link は root に近いノードから BFS 順に構築する．ノード $v$ から文字 $c$ に対応する Trie の辺が存在する場合，遷移先を $u$ とすると，$u$ の failure link は $v$ の failure link から $c$ で遷移した先となる．辺が存在しない場合は，$v$ の failure link から $c$ で遷移した先を $v$ からの遷移先とする．root に対応する遷移先が存在しない場合は root へ戻る．

各ノードには，そのノードで終端するパターンに加えて，failure link の遷移先で終端するパターンも保持する．これにより，検索時には現在のノードが保持する ID を列挙すれば，その位置で終わるすべてのパターンを取得できる．

パターンの長さの総和を $L$，failure link に沿って複製されるパターン ID 数を $K$ とすると，build() は $O(char_size\cdot L+K)$ 時間，$O(char_size\cdot L+K)$ 空間．検索文字列の長さを $N$，報告する出現数を $M$ とすると，match() は期待 $O(N+M)$ 時間，match_any() は $O(N)$ 時間．

資料

Alfred V. Aho and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search. 1975.

Verified with

verify/string/AOJ_ALDS1_14_D.test.cpp

Code

#pragma once

template <int char_size = 26, char char_start = 'a'>
struct AhoCorasick {
  struct Node {
    int prev, c, fail;
    int next[char_size];
    vector<int> accept;
    Node(int prev, int c) : prev(prev), c(c), fail(-1) {
      memset(next, -1, sizeof(next));
    }
  };

  AhoCorasick() : root(make_node()), str_count(0) {}

  int add(const string& str) {
    assert(!str.empty());
    int id = str_count++;
    int x = root;
    for (auto c : str) x = get_child(x, char_index(c));
    nodes[x].accept.emplace_back(id);
    return id;
  }
  int size() const { return str_count; }
  int node_size() const { return (int)nodes.size(); }
  int get_root() const { return root; }
  const vector<int>& accept(int x) const { return nodes[x].accept; }

  void build() {
    queue<int> qu;
    for (int i = 0; i < char_size; i++) {
      int& x = nodes[root].next[i];
      if (x == -1) {
        x = root;
      } else {
        qu.push(x);
        nodes[x].fail = root;
      }
    }
    while (!qu.empty()) {
      int x = qu.front();
      qu.pop();
      int f = nodes[x].fail;
      auto& accept_x = nodes[x].accept;
      auto& accept_f = nodes[f].accept;
      vector<int> accept;
      set_union(accept_x.begin(), accept_x.end(), accept_f.begin(), accept_f.end(), back_inserter(accept));
      swap(accept_x, accept);
      for (int i = 0; i < char_size; i++) {
        int& y = nodes[x].next[i];
        if (y == -1) {
          y = nodes[f].next[i];
        } else {
          qu.push(y);
          nodes[y].fail = nodes[f].next[i];
        }
      }
    }
  }

  int move(int x, const char c) const {
    int y = nodes[x].next[c - char_start];
    if (y == -1) y = nodes[x].fail;
    return y;
  }
  unordered_map<int, int> match(const string& s) const {
    int x = root;
    unordered_map<int, int> count;
    for (auto c : s) {
      x = move(x, c);
      for (auto id : nodes[x].accept) count[id]++;
    }
    return count;
  }
  int match_any(const string& s) const {
    int x = root;
    int count = 0;
    for (auto c : s) {
      x = move(x, c);
      count += nodes[x].accept.size();
    }
    return count;
  }

 private:
  vector<Node> nodes;
  int root, str_count;
  int make_node(int prev = -1, int c = -1) {
    nodes.push_back(Node(prev, c));
    return nodes.size() - 1;
  }
  int get_child(int index, int char_index) {
    if (nodes[index].next[char_index] == -1) {
      int child = make_node(index, char_index);
      nodes[index].next[char_index] = child;
    }
    return nodes[index].next[char_index];
  }
  int char_index(char c) const {
    int x = c - char_start;
    assert(0 <= x && x < char_size);
    return x;
  }
};

/**
 * @brief Aho-Corasick
 * @docs docs/string/aho-corasick.md
 */

#line 2 "string/aho-corasick.hpp"

template <int char_size = 26, char char_start = 'a'>
struct AhoCorasick {
  struct Node {
    int prev, c, fail;
    int next[char_size];
    vector<int> accept;
    Node(int prev, int c) : prev(prev), c(c), fail(-1) {
      memset(next, -1, sizeof(next));
    }
  };

  AhoCorasick() : root(make_node()), str_count(0) {}

  int add(const string& str) {
    assert(!str.empty());
    int id = str_count++;
    int x = root;
    for (auto c : str) x = get_child(x, char_index(c));
    nodes[x].accept.emplace_back(id);
    return id;
  }
  int size() const { return str_count; }
  int node_size() const { return (int)nodes.size(); }
  int get_root() const { return root; }
  const vector<int>& accept(int x) const { return nodes[x].accept; }

  void build() {
    queue<int> qu;
    for (int i = 0; i < char_size; i++) {
      int& x = nodes[root].next[i];
      if (x == -1) {
        x = root;
      } else {
        qu.push(x);
        nodes[x].fail = root;
      }
    }
    while (!qu.empty()) {
      int x = qu.front();
      qu.pop();
      int f = nodes[x].fail;
      auto& accept_x = nodes[x].accept;
      auto& accept_f = nodes[f].accept;
      vector<int> accept;
      set_union(accept_x.begin(), accept_x.end(), accept_f.begin(), accept_f.end(), back_inserter(accept));
      swap(accept_x, accept);
      for (int i = 0; i < char_size; i++) {
        int& y = nodes[x].next[i];
        if (y == -1) {
          y = nodes[f].next[i];
        } else {
          qu.push(y);
          nodes[y].fail = nodes[f].next[i];
        }
      }
    }
  }

  int move(int x, const char c) const {
    int y = nodes[x].next[c - char_start];
    if (y == -1) y = nodes[x].fail;
    return y;
  }
  unordered_map<int, int> match(const string& s) const {
    int x = root;
    unordered_map<int, int> count;
    for (auto c : s) {
      x = move(x, c);
      for (auto id : nodes[x].accept) count[id]++;
    }
    return count;
  }
  int match_any(const string& s) const {
    int x = root;
    int count = 0;
    for (auto c : s) {
      x = move(x, c);
      count += nodes[x].accept.size();
    }
    return count;
  }

 private:
  vector<Node> nodes;
  int root, str_count;
  int make_node(int prev = -1, int c = -1) {
    nodes.push_back(Node(prev, c));
    return nodes.size() - 1;
  }
  int get_child(int index, int char_index) {
    if (nodes[index].next[char_index] == -1) {
      int child = make_node(index, char_index);
      nodes[index].next[char_index] = child;
    }
    return nodes[index].next[char_index];
  }
  int char_index(char c) const {
    int x = c - char_start;
    assert(0 <= x && x < char_size);
    return x;
  }
};

/**
 * @brief Aho-Corasick
 * @docs docs/string/aho-corasick.md
 */

Aho-Corasick (string/aho-corasick.hpp)

アルゴリズム

資料

Verified with

Code

Aho-Corasick
(string/aho-corasick.hpp)