0

寻找最长重复子串的算法公式如下 1)build the suffix tree 2)find the deepest internal node with at least k leaf children 但我不明白为什么这是有效的，所以基本上是什么让这个算法正确？另外，我发现这个算法的来源说是在 O(n) 中找到重复的子串，其中 n 是子串的长度，这对我来说也不清楚！让我们考虑下面的树，这里最长的重复子串是“ru”，如果我们应用 DFS，它将在 5 步中找到它，而不是在 2 步中你向我解释这些东西？谢谢

图片

4

2 回答 2

0

给定一个包含N个字符的字符串S，构建相应的后缀树是O(N)（使用诸如Ukkonen's 之类的算法）。

现在，这样的后缀树最多可以有2N - 1个节点（包括根和叶）。

如果您遍历树并计算从给定节点可到达的叶子数量及其深度，您将找到所需的结果。为此，您从根开始并探索其每个子项。

一些伪代码：

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)，其中N是输入字符串的长度（而不是匹配子字符串的长度！）。

注意：上面介绍的遍历基本上就是后缀树上的一个DFS。

于 2016-11-15T15:52:30.447 回答
0

我想你完全知道O(n)（大 O 表示法）是指某个数量的增长顺序作为n的函数，而不是数量与n的等价性。
我写这个是因为阅读了我有疑问的问题......
我写这个是作为一个回答而不是评论，因为评论有点太长了（我想......）

于 2016-11-15T15:29:41.170 回答