我正在本学期学习算法，并阅读了有关Aho-Corasick字符串匹配算法和Ukkonen的用于构建后缀树的算法的信息。
我阅读了这两个文章，但无法理解这两者的主要基本区别，除了故障链接检查前缀，后缀链接检查后缀。
这两种算法有什么区别？
我认为您对后缀链接和失败链接的理解不正确。在这两种情况下，后缀/故障链接都是从trie / suffix树中的一个节点到trie / suffix树中的另一个节点的指针，其具有以下属性：如果原始节点表示字符串x，则由编码的字符串y后缀/故障链接所指向的节点是y是字符串x的最长后缀的节点。
两种算法之间的主要区别在于算法产生的内容，而不是后缀/失败链接的含义。Aho-Corasick产生了一个带有附加过渡信息的特里树，该过渡信息使尽快找到字符串集合的所有实例成为可能。产生的故障链接既可用于算法的构造，也可用于模式匹配步骤。Ukkonen的算法生成后缀树，仅在构造过程中使用后缀链接，而在大多数查询时不使用后缀链接。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句