一个基本的字符串操作练习很好的问题。我已经不记得后缀树了；）但是正如您所说的那样：从理论上讲，您已经定了。
如何预处理带有后代叶子的树？
有关该主题的Wikipedia存根有点令人困惑。您只需要知道，如果您是最外面的有`n
=
k孩子的非叶子节点。如果您在整个字符串中找到了从根节点到该节点的子字符串，则后缀树会告诉您n可能存在连续性。因此，必须有n`发生此字符串的地方。
之后，如何快速计算深度？
这个问题和许多类似问题的简单关键概念是进行深度优先搜索：在每个Node中，询问子元素的值并将其最大值返回给父元素。根节点将获得最终结果。
值的计算方式因问题而异。在这里，每个节点都有三种可能性：
- 该节点没有子节点。其叶节点，结果无效。
- 每个孩子都返回无效结果。它的最后一个非叶子节点，结果为零（此节点之后没有更多字符）。如果此节点有子节点
n
，则从根到此节点的每个边的缩合字符串n
在整个字符串中出现的次数。如果我们至少需要k
和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.sclass 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 = selfnodes = {1 : Node(1)} # root-nodestring = 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()
