algorithm - 后缀树中的后缀链接是否与 aho-corasick 自动机中的失败边相同？

Question

如果是这样，有人可以解释后缀树中后缀链接的用途，以实现精确的字符串匹配吗？

Answer 1

没有。后缀链接是后缀树中的特定转换。给定树中表示子串 (s_i) 的状态，其中 0 < i < n，从该状态出发的后缀树将导致表示子串 (s_i+1 )，其中 0 < i < (n-1)。

这些特定的转换在构建树的过程中使用，以便在您添加新角色时快速更新树的分支。顾名思义，给定一个表示字符串 S 的起始状态，如果您继续跟踪后缀链接，您将枚举出 S 的后缀。

然后...就是这样。您可以使用该信息来快速执行某些查询，但与精确的字符串匹配无关。

精确字符串匹配在后缀树中是如何工作的？你走下你的树。如果您在节点中，则必须选择良好的转换，从与您的字符串匹配的字符开始。如果没有不匹配，您可以以显式状态(节点)或隐式状态(在转换中间)结束:此时您知道输入字符串是后缀表示的字符串的子字符串树。