如果是这样，有人可以解释后缀树中后缀链接的目的以进行精确的字符串匹配吗？
问问题
226 次
1 回答
1
空无一人。后缀链接是后缀树中的特定转换。给定树中表示子串 (s i ) 的状态，且 0 < i < n，来自该状态的后缀树将导致表示子串 (s i+1 ) 的状态，其中 0 < i < (n- 1）。
在树的构建过程中使用这些特定的过渡，以便在添加新角色时快速更新树的分支。正如他们的名字所暗示的那样，给定一个表示字符串S的起始状态，如果您继续关注后缀链接，您将枚举S的后缀。
而且……就是这样。您可以使用该信息快速执行一些查询，但与精确字符串匹配无关。
精确的字符串匹配如何在后缀树中工作？你走下你的树。如果您在一个节点中，您必须选择良好的转换，从与您的字符串匹配的字符开始。如果没有不匹配，您可以最终处于显式状态（节点）或隐式状态（在转换中间）：此时您知道输入字符串是后缀表示的字符串的子字符串树。
于 2016-10-04T16:07:03.433 回答