在DAWG（而非Trie）上使用Aho-Corasick

Question

是否有人知道是否可以修改AHA-Corasick字符串匹配算法以用於DAWG（定向非循環圖表）而不是Trie？

Answer 1

Aho-Corasick算法中的trie不是簡單的單詞樹，但包含失敗函數的其他轉換（您在失配之後繼續哪些轉換）。有一種算法叫做multiBDM，它使用了一個trie和一個DAWG。您可以在本書的第7章中找到詳細信息和其他基於自動機的方法：M. Crochemore和W. Rytter，文本算法，牛津大學出版社，紐約，1994。更多相關信息，請參閱here。