最長共同子序列問題
此方法會給定2個序列,要找出兩序列之中其最長共同子序列的長度,子序列會以相同的順序出現,但不會連續出現;常會用在基因比對上面,透過此演算法,我們能得知兩基因之相似度為多少。
舉例來說:
假設我們有一組字串 A = abcde
其子序列為由A中任意刪除某些元素,包括: ad(abcde), abe(abcde), etc.
LCS演算法
我們可以使用動態規劃法(Dynamic Programming)去實作LCS,使用遞迴解,關鍵在於兩序列的最後一個字元,有兩種情況:
假設有A, B兩字串,A = a1a2…am,B = b1b2…bn
假設Lm,n代表A與B的最長共同子序列
情況一:Am = bn
這種情況下,我們每次用遞迴解到字串長度-1的部分,再+1即可。
Lm,n = Lm-1,n-1 + 1
情況二:Am != bn
這種情況下,就取max(Lm,n-1, Lm-1,n),就能使用遞迴解。
Lm,n = max(Lm,n-1, Lm-1,n)
到這裡有點搞不清楚沒關係,我們把它圖像化
假設:
A = a b c d
B = a e d
第一步我們先把構造圖畫出來,我們使用一個矩陣包含A, B兩字串,矩陣裡的第一列與第一欄皆為0,接下來由右至左,由上而下填入數字,規則如圖所示,第一點就像情況一,若Am = bn,我們每次用遞迴解到字串長度-1的部分,再+1即可,因此將數字+1;第二點就是情況二,若Am != bn,就取max(Lm,n-1, Lm-1,n),就能使用遞迴解,Lm,n-1 就是上面的值,Lm-1,n 為左方之值。
第二步就是往回找,規則如圖所示,往回找就能找到解了。
Python 3實作!
Input:
X = "abcd"
Y = "aed"
print("Lenth of LCS is:", lcs(X, Y, len(X), len(Y)))
Output:
Lenth of LCS is: 2
時間複雜度
Time complexity: O(mn)
查看GitHub原始碼(建議使用chrome開啟)