我知道这是一个有点被打败的话题,但是我已经达到了可以从已经回答的问题中得到的帮助.
这是针对Rosalind项目问题的LREP.我正在尝试在字符串中找到最长的k-peated子字符串,并且我已经提供了后缀树,这很好.我知道我需要使用每个节点的后代叶子数来注释后缀表,然后找到带有>=k后代的节点,最后找到这些节点中最深的节点.理论上我已经确定了.
我从以下资源中获得了很多帮助(哎呀,我只能发布2个):
我可以从根到每个叶子获取路径,但我无法弄清楚如何以这样的方式预处理树,以便我可以从每个节点获得后代的数量.我有一个单独的算法,适用于小序列,但它具有指数复杂性,所以对于较大的东西,它需要太长时间.我知道使用DFS我应该能够以线性复杂度执行整个任务.为了使这个算法起作用,我需要能够在不到5分钟的时间内获得长度约为40,000的最长k-peat.
这是一些示例数据(第一行: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 …