algorithm - 后缀树搜索时间

Question

有人知道下面声明的原因吗？或者有没有更好的网站来问这类问题？任何指针将不胜感激。

如果一个模式在文本（长度为 n）中出现 k 次，则在该文本的后缀树中搜索所有这些 k 次模式的成本为 O(n+k)。

Answer 1

根据您在何处找到此声明，在上下文中可能存在特定原因。

然而，'+k' 的通常原因只是需要 O(k) 额外的操作来插入您在返回给用户的结果列表中找到的每个匹配项。当使用倒排文件而不是后缀树时，情况不一定如此，因为在索引中找到的倒排列表（也称为张贴列表）已经是最终结果列表（至少如果我们假设（a）查询仅由单个令牌组成，并且（b）倒排列表未压缩存储）。

但是后缀树通常（除非它是专门准备的）不包含这样的匹配列表。因此，在匹配过程中，您确定了一条通过树的路径，在某个内部节点处结束。从那里，您必须遵循该内部节点的子树中的所有路径来识别告诉您匹配的实际位置的叶节点（每个匹配一个叶节点），并将匹配位置插入您返回的结果列表中用户。这最后一步需要 O(k) 时间。

另请注意，跟踪您找到的内部节点的子树中的所有路径可能会花费大量额外时间，其中总复杂度甚至高于 O(n+k)。这取决于是否存在从内部节点到其子树中的叶节点的任何直接指针。

Answer 2

后缀树搜索的时间长度与您正在搜索的模式的长度成正比。如果您为密西西比构建后缀树并搜索 ssi。必须执行的查找将是 3。时间是 O(n)，其中 n 是模式的长度。