在DAWG而不是Trie上使用Aho-Corasick

Question

有没有人知道是否有可能将Aho-Corasick字符串匹配算法修改为用于DAWG (有向无环词图)而不是Trie？

Answer 1

Aho-Corasick算法中的trie不是单词的简单trie，而是包含失败函数的附加转换(在不匹配后继续执行的位置)。有一种称为multiBDM的算法，它同时使用了trie和DAWG。您可以在本书的第7章中找到详细信息和其他基于自动机的方法:M.Crochemore和W.Rytter，文本算法，牛津大学出版社，纽约，1994年。你可以在here上找到更多关于它的信息。