Aho-Corasick 法
(String/AhoCorasick.py)

• View this file on GitHub
• Last update: 2022-01-22 12:11:49+09:00

使い方

AhoCorasick()
空の Trie 木を初期構築する。計算量 $O(1)$

• add(pattern: str) -> None
  パターン文字列 $P$ (pattern) を Trie 木に追加する。計算量 $O(|P|)$

• build_pma() -> None
  Trie 木に追加されたパターン文字列 $P_0, P_1, \cdots, Pn$ 対してパターンマッチングオートマトンを構築する。計算量 $O(\sum |P_i|)$

• match_count(text: str) -> int
  テキスト文字列 $T$ (text) に現れるパターン文字列の総数を返す。計算量 $O(|T|)$

Verified with

• TestCase/yukicoder/yuki0430.aho_corasick.test.py

Code

# from collections import deque
from standard_library.collections import deque


class Node:
    def __init__(self):
        self.child = {}
        self.failure = None
        self.valid = 0

    def set_child(self, s):
        self.child[s] = Node()

    def get_child(self, s):
        if s not in self.child:
            return None
        return self.child[s]


class AhoCorasick:
    def __init__(self):
        self.root = Node()

    def add(self, pattern):
        ptr = self.root
        for s in pattern:
            if ptr.get_child(s) is None:
                ptr.set_child(s)
            ptr = ptr.get_child(s)
        ptr.valid += 1

    def build_pma(self):
        queue = deque()
        for s in self.root.child:
            ptrch = self.root.child[s]
            ptrch.failure = self.root
            queue.append(ptrch)
        while queue:
            ptr = queue.popleft()
            ptr.valid += ptr.failure.valid
            for s in ptr.child:
                ptrch = ptr.child[s]
                f = ptr.failure
                while f is not None and f.get_child(s) is None:
                    f = f.failure
                ptrch.failure = f.get_child(s) if f is not None else self.root
                queue.append(ptrch)

    def match_count(self, text):
        ptr = self.root
        res = 0
        for s in text:
            while ptr is not None and ptr.get_child(s) is None:
                ptr = ptr.failure
            ptr = ptr.get_child(s) if ptr is not None else self.root
            res += ptr.valid
        return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page