Aho-Corasick 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /aho-corasick#noredirect を利用してください。
name
Aho-Corasick 法
short description
Aho-Corasick 法とは、複数のパターン文字列をまとめて扱える文字列検索アルゴリズムのひとつ。まず前処理として、固定された $k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ たちから Trie 木を作り、その上に適切に辺を張って $O(\sum \vert P_i \vert)$ でオートマトンを作る。このオートマトンを利用して、与えられたテキスト文字列 $T$ に対して $O(\vert T \vert)$ で検索を行う。
input
パターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ とテキスト文字列 $T$
output
パターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ のどれがテキスト文字列 $T$ に含まれるか。含まれるならその位置も求める。
time complexity
アルファベット $\Sigma$ の大きさは定数であるとして、前処理には $O(\sum \vert P_i \vert)$ で検索には $O(\vert T \vert)$

概要

Aho-Corasick 法とは、複数のパターン文字列をまとめて扱える文字列検索アルゴリズムのひとつ。計算量はアルファベット $\Sigma$ の大きさにも依存するが、ここでは $\Sigma$ を固定し大きさは定数としておく。まず前処理として、固定された $k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ たちから Trie 木を作り、その上に適切に辺を張って $O(\sum \vert P_i \vert)$ でオートマトンを作る。このオートマトンを利用して、与えられたテキスト文字列 $T$ に対して $O(\vert T \vert)$ で検索を行う。

詳細

(省略)

メモ

参考文献

関連項目

外部リンク