后缀链接和失败链接有什么区别？

Question

这学期我正在学习算法，并且读过关于建立后缀树的Aho-Corasick字符串匹配算法和Ukkonen算法的文章。

我读了这两篇文章，但不能理解这两者的主要基本区别，除了失败链接检查前缀和后缀链接检查后缀。

这两种算法有什么区别？

Answer 1

我认为你对后缀链接和失败链接的理解是不正确的。在这两种情况下，后缀/失败链接都是从trie/后缀树中的一个节点指向具有以下属性的trie/后缀树中的另一个节点的指针:如果原始节点表示字符串x，则由后缀/失败链接指向的节点编码的字符串y是字符串x的最长后缀。

这两种算法的主要区别在于算法产生了什么，而不是后缀/失败链接意味着什么。Aho生成一个带有额外转换信息的trie注释，从而能够尽快找到字符串集合的所有实例。在算法的构造和模式匹配步骤中都使用了产生的故障链接。Ukkonen的算法生成一个后缀树，只在构造时使用后缀链接，而不是在树上的大多数查询中使用。

希望这能有所帮助！

Answer 2

不同之处是后缀/字典链接就像指向子元素父级的指针一样。失败链接来自广度优先搜索。这两个链接都是后缀。