【ROSALIND】【练Python，学生信】61 寻找序列中最长的多次重复

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

寻找最长的多次重复（Finding the Longest Multiple Repeat）

Given: A DNA string s (of length at most 20 kbp) with $ appended, a positive integer k, and a list of edges defining the suffix tree of s. Each edge is represented by four components:

1. the label of its parent node in T(s);

2. the label of its child node in T(s);

3. the location of the substring t of s∗ assigned to the edge; and

4. the length of t.

所给：一条DNA序列s，长度不超过20kb，尾部添加$；一个正整数k；以及一个列表，其中包含的信息定义了s的后缀树中的每条边，每条边的信息包含以下四个部分：

1. 其在T(s)中的父结点的标签；

2. 其在T(s)中的子结点的标签；

3. 这条边上的子串t在s上的起始位置；

4. 子串t的长度。

Return: The longest substring of s that occurs at least k times in s. (If multiple solutions exist, you may return any single solution.)

需得：s的一条子串，这条子串必须在s中出现至少k次，长度要尽量长。（如果有多个结果符合，任意给出一个即可）

测试数据

CATACATAC$

2

node1 node2 1 1

node1 node7 2 1

node1 node14 3 3

node1 node17 10 1

node2 node3 2 4

node2 node6 10 1

node3 node4 6 5

node3 node5 10 1

node7 node8 3 3

node7 node11 5 1

node8 node9 6 5

node8 node10 10 1

node11 node12 6 5

node11 node13 10 1

node14 node15 6 5

node14 node16 10 1

测试输出

CATAC

计算机背景

        在53 Trie树与模式匹配中，我们已经初步了解了Trie树这种数据结构，Trie树常用于同时处理多个字符串。如果我们想要对单条序列进行处理，后缀树（suffix tree）是一种更理想的结构。有关后缀树的介绍请参考这一篇博文：https://blog.csdn.net/fanzitao/article/details/8042015。

        下图是一个后缀树的例子：

        s的后缀树用T(s)表示，定义如下：

•     T(s)为有根树，有n个叶子结点；

•     T（s）的每一条边的标签都是s*的子串, s∗ 是通过在s的末尾添加$形成的字符串；

•     T（s）的每个内部结点（根结点除外）都至少有两个子结点；

•     从某个结点到其不同子结点的边，作为标签的子串必以不同的字符开头；

•     沿着边连接子串，从根到叶的每条路径都对应于s∗的一条唯一的后缀。

思路

        又是一道我解不出来只能作弊的题目，本文全部代码来自https://github.com/fedeoliv/Rosalind-Problems/blob/142f9f44682c53ae1016c09e14bb51f42beca06a/lrep.py。

我在这里揣测一下大神的解题思路。

        题目可以分为两部分：第一是根据所给的信息构建出后缀树；第二是遍历整棵树后找到最长的重复子串。

        首先看如何构建后缀树，这里大神用了一个类来保存每个边的信息，值得注意的是，s这个对象是个集合，其中可以把该边所有子结点的信息存储下来。Pop可以从左侧取出集合的第一个元素，这样就恰好把以node1为起始的整棵树都取出来了，存在root中，作为参数传入get_longest_substring函数中。

        get_longest_substring函数的作用就是遍历整棵树找出最长重复字串。从根结点开始，用递归的方式，对分枝的数量进行统计，因为分枝就意味着重复。再通过不断比较，记录最长的重复结果，最终把组成最长子串的几条边的起止位置返回，连接输出即为最终结果。

        这道题对我来说难度很大，我是一步一步运行着看结果才理解了个大概，因此我很难解释清楚。如果各位看官也和我一样，建议先在纸上画出所给测试数据的后缀树，然后用Debugger功能观察一下变量的变化。如果有问题或更好的解释，也欢迎评论区交流。

代码