我知道这是一个比较棘手的话题，但是我已经从已经回答的内容中获得了最大的帮助。
这是针对Rosalind项目问题LREP的。我试图在字符串中找到最长的k- peated子字符串，并且 提供 了后缀树，这很好。我知道我需要用每个节点的后代叶子数注释后缀表，然后找到具有>=k后代的节点，最后找到这些节点中最深的节点。从理论上讲，我已经做好了准备。
>=k
我可以获取从根到每个叶子的路径，但是我无法弄清楚如何以可以从每个节点获取后代数量的方式对树进行预处理。我有一个单独的算法可以处理较小的序列，但是它的计算复杂度是指数级的，因此对于较大的算法，它花费的时间太长。我知道使用DFS，我应该能够以线性复杂度执行整个任务。为了使该算法起作用，我需要能够在不到5分钟的时间内获得约40,000长字符串的最长k-peat。
以下是一些示例数据（第一行：sequence，第二行：k，后缀表格式：）parent child location length：
sequence
k
parent child location length
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。
CATAC
使用以下代码（从LiteratePrograms修改），我已经能够获取路径，但是在较长的序列上仍然需要很长时间才能解析出每个节点的路径。
#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
我想做的是descendants >= k在查找深度之前对树进行预处理，以找到满足要求的节点。我什至还不知道如何计算深度。虽然我想我会拥有一些字典来跟踪路径中每个节点的深度然后求和。
descendants >= k
因此，我最重要的问题是： “如何预处理带有后代叶子的树？”
我的次要问题是： “在那之后，我如何快速计算深度？”
附言：我应该说这 不是 家庭作业或任何类似的事情。我只是一个生化专家，试图通过一些计算挑战来拓展自己的视野。
一个基本的字符串操作练习很好的问题。我已经不记得后缀树了；）但是正如您所说的那样：从理论上讲，您已经定了。
有关该主题的Wikipedia存根有点令人困惑。您只需要知道，如果您是最外面的有`n
= k孩子的非叶子节点。如果您在整个字符串中找到了从根节点到该节点的子字符串，则后缀树会告诉您n可能存在连续性。因此，必须有n`发生此字符串的地方。
孩子的非叶子节点。如果您在整个字符串中找到了从根节点到该节点的子字符串，则后缀树会告诉您
可能存在连续性。因此，必须有
这个问题和许多类似问题的简单关键概念是进行深度优先搜索：在每个Node中，询问子元素的值并将其最大值返回给父元素。根节点将获得最终结果。
值的计算方式因问题而异。在这里，每个节点都有三种可能性：
n
k > n
当然，您还必须返回对应的结点。否则，您将知道最长的重复子字符串多长时间，但不知道它在哪里。
您应该首先尝试自己编写代码。如果您想收集所有必要的信息，则构造树很简单，但并非易事。不过，这是一个简单的示例。请注意：如果输入某种程度上无效，则将放弃所有的完整性检查，并且一切都会可怕地失败。例如，不要尝试使用除根索引以外的任何其他根索引，不要将节点引用为父节点，而之前未将其引用为子节点，等等。还有很大的改进空间 提示 ;）。
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()
