我在这学期学习算法，并阅读了关于Aho-Corasick 字符串匹配算法和Ukkonen构建后缀树的算法。
我阅读了它们，但无法理解这两者的主要基本区别，除了失败链接检查前缀和后缀链接检查后缀。
这两种算法有什么区别？
问问题
1418 次
2 回答
2
我认为你对后缀链接和失效链接的理解是不正确的。在这两种情况下，后缀/失败链接都是从 trie/后缀树中的一个节点到 trie/后缀树中的另一个节点的指针，具有以下属性：如果原始节点表示字符串 x，则字符串 y 由后缀/失败链接指向的节点是 y 是字符串 x 的最长可能后缀的节点。
两种算法之间的主要区别在于算法产生的内容，而不是后缀/失败链接的含义。Aho-Corasick 生成了一个带有额外转换信息注释的 trie，它可以尽可能快地找到字符串集合的所有实例。产生的故障链接用于算法的构建和模式匹配步骤。Ukkonen 的算法生成后缀树，仅在构造期间使用后缀链接，而不是在树上的大多数查询期间使用。
希望这可以帮助！
于 2013-11-01T02:24:58.530 回答
1
不同之处在于后缀/字典链接就像指向孩子的父母的指针。失败链接来自广度优先搜索。两个链接都是后缀。
于 2015-02-18T13:44:29.050 回答