当前位置: 首页 > 知识库问答 >
问题:

最长重复(k次)子串

燕野
2023-03-14

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

这是针对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.我应该声明这不是家庭作业或诸如此类的东西。我只是一个生物化学家,试图通过一些计算挑战来拓展我的视野。


共有1个答案

芮瑾瑜
2023-03-14

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

关于这个主题的维基百科存根有点混乱。您只需要知道,您是否是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()

 类似资料:
  • 解决此问题的最佳方法(性能方面)是什么?有人建议我使用后缀树。这是最好的方法吗?

  • 我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题,因为他指的是一个链接,该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。 假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。 示例:N=9,K=1 A=[3,9,4,5,8,6,1,3,7] 答案:7 说明: 最长递增子序列为:3,4,5,8(或6),

  • 我正在寻找一种快速算法,搜索给定字符串中最长的重复子字符串(至少重复1次),并尽可能降低时间复杂度和(如果可能)内存(RAM)。 我见过一些实现,但大多数都不是为大量字符设计的(比如说)。一个例子是: 我已经尝试了100次包含的字符串。 它适用于小弦( 编辑:有没有办法不用在内存中加载一个(比如20GB)文件就可以做到这一点?

  • 我正在考虑这个leetcode问题,在完成这个天真的方法时遇到了一个问题。我在这里找到了一个最佳的解决方案。但我不确定我天真的尝试到底出了什么问题。 问题如下: 给定两个整数数组A和B,返回两个数组中出现的子数组的最大长度。 示例: 输入:A:[1,2,3,2,1]B:[3,2,1,4,7] 输出:3 说明:最大长度的重复子数组为[3,2,1]。 这是我当前的代码: 我的解决方案通过了几个测试用例

  • 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",

  • 给定一个数组< code>a[0..< code>0之间的整数的N-1] 例: 输入 预期输出: