AhoCorasickを実装してみたんだす
今更ながら「大規模サービス技術者入門」を読み返したんだす。
AhoCorasickのこと今までアホコラシックて読んでたけど、
正しくはエイホコラシック(Wikipedia調べ)だそうなんだす。
ソースコード -> pyahocorasick
failure linkを作るところを理解するのに時間がかかった。
トライ木を構築した後、根から順繰りに次ぎのノードを見てって、最長接尾辞を決定するところ。
再帰でつくってみた。
最終的にこんな感じでテスト。