我知道这是一个有点老生常谈的话题,但我已经达到了从已经得到的答案中得到的帮助的极限。
这是针对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.我应该声明这不是家庭作业或诸如此类的东西。我只是一个生物化学家,试图通过一些计算挑战来拓展我的视野。
对于基本字符串操作的练习来说,这是一个不错的问题。我不再记得后缀树了;)但正如你所说:从理论上讲,你已经准备好了。
关于这个主题的维基百科存根有点混乱。您只需要知道,您是否是n的最外层非叶节点
对于这一问题和许多类似问题,一个简单的关键概念是进行深度优先搜索:在每个节点中,询问子元素的值,并将最大值返回给父元素。根节点将获得最终结果。
计算值的方式因问题而异。在这里,每个节点都有三种可能:
节点没有子节点。它是一个叶节点,结果无效。
每个子级返回无效结果。它是最后一个非叶子节点,结果为零(此节点后不再有字符)。如果此节点有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] 例: 输入 预期输出: