最长重复的子串，至少有k次出现的正确性

查找最长重复子串的算法公式如下 1)build the suffix tree 2)find the deepest internal node with at least k leaf children 但我不明白为什么这个工作正常，所以基本上是什么让这个算法正确？还有，我发现这个算法说，在O（n）中找到重复的子字符串，其中n是子字符串的长度，这对我也不是很清楚！让我们考虑下面的树，这里最长的重复子字符串是“ru”，如果我们应用DFS它会在5步中找到它，但不在2中你能向我解释这个东西吗？感谢最长重复的子串，至少有k次出现的正确性

image

来源

2016-11-15 ro.Loon

由于后缀树构造在字符串本身的长度上是线性的，因此它在子字符串的长度中不能是线性的 – Rerito

我想你完全知道O(n)（大O符号）是指一些数量的增长的顺序为ñ的功能，而不是数量与等价n。
我写这篇文章becase的阅读问题，我怀疑...
我在写这为aswer，而不是评论，因为它是一个评论有点太长了（我想...）

来源

2016-11-15 15:29:41 MarcoS

给定字符串S的否字符，构建相应的后缀树是O（N）（使用诸如Ukkonen's的算法）。

现在，这样的后缀树可以有at most 2N - 1 nodes（包括根和树叶）。

如果遍历树并计算从给定节点到达的树叶数及其深度，则可以找到所需的结果。要做到这一点，你需要从根开始并探索每个孩子。

一些伪代码：

traverse(node, depth): 
    nb_leaves <-- 0 
    if empty(children(node)): 
     nb_leaves <-- 1 
    else: 
     for child in children(node): 
      nb_leaves <-- nb_leaves + traverse(child, depth+1) 
    node.setdepth(depth) 
    node.setoccurrences(nb_leaves) 
    return nb_leaves

初始呼叫是traverse(root, 0)。由于结构是树，因此每个节点只有一个调用traverse。这意味着traverse的最大呼叫数是2N - 1，因此整体遍历只有O（N）。现在您只需跟踪最大深度的节点，并通过添加相关簿记机制来验证：depth > 0 && nb_leaves >= k。这并不妨碍整体的复杂性。

在结束时，算法的复杂度，以找到这样一个子字符串是O（N）其中Ñ是输入字符串的长度（和不匹配子串的长度！）。

注：上述遍历基本上是后缀树上的DFS。

来源

2016-11-15 15:52:30 Rerito

最长重复的子串，至少有k次出现的正确性

回答

相关问题