有人知道以下陈述的原因吗?还是有一个更好的网站来问这类问题?任何指针都将不胜感激。
如果一个模式出现在文本中(长度n) k次,则搜索该文本后缀树中的所有k次将花费O(n+k).
。
发布于 2011-04-28 14:33:29
后缀树搜索的时间长度与正在搜索的模式的长度成正比。如果您为密西西比构建后缀树并搜索ssi。必须执行的查找是3,时间是O(n),其中n是模式的长度。
发布于 2012-03-04 17:09:28
根据您在何处找到该语句,在上下文中可能有特定的原因说明它是正确的。
但是,“+k”通常的原因仅仅是需要额外的O(k)操作来插入返回给用户的结果列表中的每个匹配项。当使用倒排文件而不是后缀树时,情况不一定如此,因为索引中的倒排列表(也称为公告列表)已经是最终的结果列表(至少如果我们假设(a)查询只包含一个令牌,(b)倒排列表是未压缩的)。
但是后缀树通常(除非是特别准备的)不包含这样的匹配列表。因此,在匹配过程中,您可以通过树标识路径,结束于某个内部节点。从那里开始,您必须跟踪该内部节点的子树中的所有路径,以标识告诉您匹配的实际位置(每个匹配的一个叶节点)的叶节点,并在返回给用户的结果列表中插入匹配位置。这最后一步需要O(k)时间。
还请注意,跟踪内部节点子树中的所有路径可能会花费大量额外时间,其中总复杂度甚至高于O(n+k)。这取决于是否有从内部节点到子树中的叶节点的直接指针。
https://stackoverflow.com/questions/5820153
复制相似问题