最長的子串（對於三元組序列）

Question

我想比較格式的字符串：AAA-ABC-LAP-ASZ-ASK;基本上，用破折號分隔的三個字母。

我試圖找到2個這樣的任意長度（從1到30三胞胎）序列之間的最長序列的共同三胞胎。例如，可以發現5個（BBB-AAA-DDD-EEE-BBB，偶數）序列的AAA-BBB-CCC-AAA-DDD-EEE-BBB和BBB-AAA-DDD-EEE-BBB。如果CCC不存在於第二序列中）。

破折號不應被視爲比較;他們只用來分隔三胞胎。

我使用Python，但只是一般的算法來實現這一目標應該做的:)

Answer 1

作爲開始，你至少可以通過計算set symmetric difference減少的問題，以消除不發生兩三胞胎任何序列。

對於最長的子序列，算法使用dynamic programming方法。對於每個三元組，找到兩者中出現的最短的長度爲2的子串。循環這些對，試圖通過組合對來擴展它們。繼續擴展，直到您擁有每個三元組的最長擴展。挑選最長的那些：

ABQACBBA 
ZBABBA 

Eliminate symmetric difference 
ABABBA and BABBA 


Start with the first A in ABABBA. 
It is followed by B, giving the elements [0,1] 
Check to see if AB is in BABBA, and record a match at [1,2] 
So, the first pair is ((0,1), (1,2)) 

Next, try the first B in ABABBA. 
It is followed by an A giving the elements [1,2] 
Check to see if BA is in BABBA and record a match at [0,1] 

Continue with the rest of the letters in ABABBA. 

Then, try extensions. 

The first pair AB at [0,1] and [1,2] can be extended from BA 
to ABA [0,1,3] and [1,2,4]. Note, the latter group is all the 
way to the right so it cannot be extended farther. ABA cannot 
be extended. 

Continue until all sequences have extended are far as possible. 
Keep only the best of those. 

Answer 2

Sequence alignment算法，常用於生物信息使用，可以在這裏使用。它們主要用於對齊單字符序列，但可以修改它們以接受n字符序列。 Needleman–Wunsch algorithm是一個相當有效的。

Answer 3

我認爲您正在尋找Longest Common Subsequence算法，該算法可以非常快速地找到該序列（在O（n ）時間）。該算法基於簡單的動態規劃循環，並且有許多在線的例子可以實現算法。

直觀，算法使用的作品通過查看每個序列的第一三線工程下列遞歸分解：

• 如果兩個序列是空的，最長公共子是空序列。
• 否則：
  • 如果每個序列匹配的第一三胞胎，該LCS是該元素隨後兩個序列的餘數的LCS。
  • 如果不是，則LCS是以下中較長的一個：第一個序列的LCS和除第一個序列的第一個元素外的所有LCS，或者第二個序列的LCS和除第一個序列的第一個元素外的所有LCS。

希望這有助於！