如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

尋找最長的多次重復(fù)（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，尾部添加$；一個正整數(shù)k；以及一個列表，其中包含的信息定義了s的后綴樹中的每條邊，每條邊的信息包含以下四個部分：

1. 其在T(s)中的父結(jié)點的標簽；

2. 其在T(s)中的子結(jié)點的標簽；

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中出現(xiàn)至少k次，長度要盡量長。（如果有多個結(jié)果符合，任意給出一個即可）

?

測試數(shù)據(jù)

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樹與模式匹配中，我們已經(jīng)初步了解了Trie樹這種數(shù)據(jù)結(jié)構(gòu)，Trie樹常用于同時處理多個字符串。如果我們想要對單條序列進行處理，后綴樹（suffix tree）是一種更理想的結(jié)構(gòu)。有關(guān)后綴樹的介紹請參考這一篇博文：https://blog.csdn.net/fanzitao/article/details/8042015。

? ? ? ??下圖是一個后綴樹的例子：

? ? ? ??s的后綴樹用T(s)表示，定義如下：

• ????T(s)為有根樹，有n個葉子結(jié)點；

• ????T（s）的每一條邊的標簽都是s*的子串, s? 是通過在s的末尾添加$形成的字符串；

• ????T（s）的每個內(nèi)部結(jié)點（根結(jié)點除外）都至少有兩個子結(jié)點；

• ????從某個結(jié)點到其不同子結(jié)點的邊，作為標簽的子串必以不同的字符開頭；

• ????沿著邊連接子串，從根到葉的每條路徑都對應(yīng)于s?的一條唯一的后綴。

?

思路

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

我在這里揣測一下大神的解題思路。

? ? ? ??題目可以分為兩部分：第一是根據(jù)所給的信息構(gòu)建出后綴樹；第二是遍歷整棵樹后找到最長的重復(fù)子串。

? ? ? ??首先看如何構(gòu)建后綴樹，這里大神用了一個類來保存每個邊的信息，值得注意的是，s這個對象是個集合，其中可以把該邊所有子結(jié)點的信息存儲下來。Pop可以從左側(cè)取出集合的第一個元素，這樣就恰好把以node1為起始的整棵樹都取出來了，存在root中，作為參數(shù)傳入get_longest_substring函數(shù)中。

? ? ? ??get_longest_substring函數(shù)的作用就是遍歷整棵樹找出最長重復(fù)字串。從根結(jié)點開始，用遞歸的方式，對分枝的數(shù)量進行統(tǒng)計，因為分枝就意味著重復(fù)。再通過不斷比較，記錄最長的重復(fù)結(jié)果，最終把組成最長子串的幾條邊的起止位置返回，連接輸出即為最終結(jié)果。

? ? ? ??這道題對我來說難度很大，我是一步一步運行著看結(jié)果才理解了個大概，因此我很難解釋清楚。如果各位看官也和我一樣，建議先在紙上畫出所給測試數(shù)據(jù)的后綴樹，然后用Debugger功能觀察一下變量的變化。如果有問題或更好的解釋，也歡迎評論區(qū)交流。

?

代碼