java - TrieではなくDAWGでAho-Corasickを使用する

Question

TrieではなくDAWG（Directed Acyclic Word Graph）で使用されるようにAho-Corasick文字列マッチングアルゴリズムを変更できるかどうか誰かが知っていますか？

Answer 1

Aho-Corasickアルゴリズムのトライは、単語の単純なトライではありませんが、失敗関数の追加の遷移が含まれています（不一致の後にどこで続行しますか）。トライとDAWGの両方を使用するmultiBDMと呼ばれるアルゴリズムがあります。詳細およびその他のオートマトンベースのアプローチは、本の第7章にあります。M.CrochemoreおよびW. Rytter、テキストアルゴリズム、オックスフォード大学出版局、ニューヨーク、1994年。詳細については、こちらをご覧ください。