最长重复（k次）子串

Question

我知道这是一个有点老生常谈的话题，但我已经达到了从已经得到的答案中得到的帮助的极限。

这是针对Rosalind项目问题LREP的。我试图找到字符串中最长的k-peated子串，我得到了后缀树，这很好。我知道我需要用每个节点的后代叶子数来注释后缀表，然后用找到节点

我从以下资源中得到了很多帮助（哦，我只能发布2条）：

• 查找字符串中最长的重复序列
• 深度优先搜索（Python）

我可以得到从根到每个叶子的路径，但是我不知道如何预处理树，这样我就可以得到每个节点的后代数量。我有一个单独的算法，可以处理小序列，但它的复杂度是指数级的，所以对于大序列来说，它需要很长时间。我知道有了DFS，我应该能够以线性复杂性执行整个任务。为了让这个算法发挥作用，我需要能够在不到5分钟的时间内获得大约40,000长字符串中最长的k-peat。

以下是一些示例数据（第一行：sequence，第二行：k，后缀表格式：父子位置长度）：

CATACATAC$
2
1 2 1 1
1 7 2 1
1 14 3 3
1 17 10 1
2 3 2 4
2 6 10 1
3 4 6 5
3 5 10 1
7 8 3 3
7 11 5 1
8 9 6 5
8 10 10 1
11 12 6 5
11 13 10 1
14 15 6 5
14 16 10 1

此操作的输出应为CATAC。

使用下面的代码（从文学程序中修改），我已经能够获得路径，但是在较长的序列中仍然需要很长时间来解析每个节点的路径。

#authors listed at
#http://en.literateprograms.org/Depth-first_search_(Python)?action=history&offset=20081013235803
class Vertex:
    def __init__(self, data):
        self.data = data
        self.successors = []

def depthFirstSearch(start, isGoal, result):
    if start in result:
        return False

    result.append(start)

    if isGoal(start):
        return True
    for v in start.successors:
        if depthFirstSearch(v, isGoal, result):
            return True

    # No path was found
    result.pop()
    return False

def lrep(seq,reps,tree):
    n = 2 * len(seq) - 1
    v = [Vertex(i) for i in xrange(n)]
    edges = [(int(x[0]),int(x[1])) for x in tree]
    for a, b in edges:
        v[a].successors.append(v[b])

    paths = {}
    for x in v:
        result = []
        paths[x.data] = []
        if depthFirstSearch(v[1], (lambda v: v.data == x.data), result):
            path = [u.data for u in result]
            paths[x.data] = path

我想做的是对树进行预处理，以找到满足子体的节点

所以，我的第一个最重要的问题是：“我如何用后代叶子预处理树？”

我的第二个不太重要的问题是：“在那之后，我如何快速计算深度？”

P. S.我应该声明这不是家庭作业或诸如此类的东西。我只是一个生物化学家，试图通过一些计算挑战来拓展我的视野。




Answer 1

对于基本字符串操作的练习来说，这是一个不错的问题。我不再记得后缀树了；）但正如你所说：从理论上讲，你已经准备好了。

关于这个主题的维基百科存根有点混乱。您只需要知道，您是否是n的最外层非叶节点

对于这一问题和许多类似问题，一个简单的关键概念是进行深度优先搜索：在每个节点中，询问子元素的值，并将最大值返回给父元素。根节点将获得最终结果。

计算值的方式因问题而异。在这里，每个节点都有三种可能：

1. 节点没有子节点。它是一个叶节点，结果无效。
2. 每个子级返回无效结果。它是最后一个非叶子节点，结果为零（此节点后不再有字符）。如果此节点有n子节点，则从根到此节点的每个边的缩略字符串在整个字符串中出现n次。如果我们至少需要k节点和k

当然，还必须返回对应的节点。否则，您将知道最长的重复子串有多长，但不知道它在哪里。

您应该先尝试自己编写代码。如果您想收集所有必要的信息，那么构建树很简单，但不是很简单。然而，这里有一个简单的例子。请注意：如果输入无效，每一次健全性检查都会被取消，一切都会严重失败。例如，不要尝试使用除一个之外的任何其他根索引，不要将节点作为父节点引用，这些节点以前没有作为子节点引用过，等等。有很大的改进空间*提示；）*。

class Node(object):
    def __init__(self, idx):
        self.idx = idx     # not needed but nice for prints 
        self.parent = None # edge to parent or None
        self.childs = []   # list of edges

    def get_deepest(self, k = 2):
        max_value = -1
        max_node = None
        for edge in self.childs:
            r = edge.n2.get_deepest()
            if r is None: continue # leaf
            value, node = r
            value += len(edge.s)
            if value > max_value: # new best result
                max_value = value
                max_node = node
        if max_node is None:
            # we are either a leaf (no edge connected) or 
            # the last non-leaf.
            # The number of childs have to be k to be valid.
            return (0, self) if len(self.childs) == k else None
        else:
            return (max_value, max_node)

    def get_string_to_root(self):
        if self.parent is None: return "" 
        return self.parent.n1.get_string_to_root() + self.parent.s

class Edge(object):
    # creating the edge also sets the correspondending
    # values in the nodes
    def __init__(self, n1, n2, s):
        #print "Edge %d -> %d [ %s]" % (n1.idx, n2.idx, s)
        self.n1, self.n2, self.s = n1, n2, s
        n1.childs.append(self)
        n2.parent = self

nodes = {1 : Node(1)} # root-node
string = sys.stdin.readline()
k = int(sys.stdin.readline())
for line in sys.stdin:
    parent_idx, child_idx, start, length = [int(x) for x in line.split()]
    s = string[start-1:start-1+length]
    # every edge constructs a Node
    nodes[child_idx] = Node(child_idx)
    Edge(nodes[parent_idx], nodes[child_idx], s)

(depth, node) = nodes[1].get_deepest(k)
print node.get_string_to_root()