Aho-Corasick(エイホ–コラシック法)
(string/aho-corasick.hpp)
概要
複数文字列に対するパターンマッチングオートマトンを構築する.
Trie のそれぞれのノードがオートマトンのある状態に相当する.
使い方
-
build()
: 現在のTrieをもとにオートマトンを構築する.
-
match(str, now)
: 現状態が now
で, 文字列 str
が現れた時に, 新たに各パターン文字列にマッチした回数を返す.
-
move(c, now)
: 現状態が now
で, 文字 c
が現れたときに, 新たにパターン文字列にマッチした個数と, 次状態を返す.
計算量
-
build()
: パターン文字列の長さの総和
- クエリ: $O(1)$
Verified with
Code
Back to top page