Aho-Corasick で 2 次元パターンマッチング

これは IQ が 1 Advent Calendar の 21 日目の記事です。

adventar.org

20 日目は 

k3ntaroo.hatenablog.com

 

Aho-Corasick とは

chakku.hatenablog.com

この Aho-Corasick を使って 2 次元の文字列の中からパターンを探す方法を書く。

やり方

下にあるテキスト T からパターン P を検索する場合を例に説明する。

f:id:tobya:20171220213627p:plain

パターン P を行単位で区切り、 Aho-Corasick を使ってパターンマッチングオートマトンを構築する。そうすると下の図のようなオートマトンができる。さらにこのオートマトンの、各行の文字列を受理する状態番号を覚えておく。

f:id:tobya:20171220213712p:plain

次にテキスト T を行単位で区切り、オートマトンに流し込む。この時に状態遷移の番号を新しいテキスト T' として覚えておく。

f:id:tobya:20171220213728p:plain

この T' をよく見ると T の中でパターンが現れる箇所の一番右の列の箇所が最初に覚えておいたパターンの受理状態の番号になっているので、KMP とかで探す。

f:id:tobya:20171220213758p:plain

Pattern Search | Aizu Online Judge で試せる。

実装

参考文献