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

Question

有人知道是否可以修改 Aho-Corasick 字符串匹配算法以用于 DAWG（有向无环词图）而不是 Trie 吗？

Answer 1

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