最长重复（k次）子字符串

最长重复（k次）子字符串

一个基本的字符串 *** 作练习很好的问题。我已经不记得后缀树了；）但是正如您所说的：从理论上讲，您已经定格。

如何预处理带有后代叶子的树？

有关该主题的Wikipedia存根有点令人困惑。您只需要知道，如果您是最外面的有`n

=
k

孩子的非叶子节点。如果您在整个字符串中找到了从根节点到该节点的子字符串，则后缀树会告诉您

n

可能存在连续性。因此，必须有

n`发生此字符串的地方。

之后，如何快速计算深度？

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

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

1. 该节点没有子节点。它是一个叶节点，结果无效。
2. 每个孩子都返回无效结果。其最后一个非叶节点，结果为零（此节点之后没有更多字符）。如果此节点有子节点

   n

   ，则从根到此节点的每个边的缩进字符串

   n

   在整个字符串中出现的次数。如果我们至少需要

   k

   节点和

   k > n

   ，则结果也是无效的。
3. 一个或多个叶子返回有效的东西。结果是返回值的最大值 加上 边缘附加到其上的字符串的长度。

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

码

您应该首先尝试自己编写代码。如果您想收集所有必要的信息，则构造树很简单，但并不简单。不过，这是一个简单的例子。请注意：如果输入某种程度上无效，则将放弃所有的完整性检查，并且一切都会可怕地失败。例如，不要尝试使用除根索引以外的任何其他根索引，不要将节点引用为父节点，而之前未将其引用为子节点，等等。还有很大的改进空间
提示 ;）。

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()