【Python】最長公共子序列LCS

LCS的定義

最長公共子序列，即Longest Common Subsequence，LCS。

一個序列S任意删除若幹個字元得到新序列T，則T叫做S的子序列；

兩個序列X和Y的公共子序列中，長度最長的那個，定義為X和Y的最長公共子序列。

字元串13455 與245576的最長公共子序列為455

字元串acdfg與adfc的最長公共子序列為adf

注意差別最長公共子串(Longest Common Substring)最長公共字串要求連續

LCS的意義

求兩個序列中最長的公共子序列算法，廣泛的應用在圖形相似處理、媒體流的相似比較、計算生物學方面。生物學家常常利用該算法進行基因序列比對，由此推測序列的結構、功能和演化過程。

LCS可以描述兩段文字之間的“相似度”，即它們的雷同程度，進而能夠用來辨識抄襲。另一方面，對一段文字進行修改之後，計算改動前後文字的最長公共子序列，将除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準确。簡而言之，百度知道、百度百科都用得上。

LCS的記号

字元串X，長度為m，從1開始數；

字元串Y，長度為n ，從1開始數；

Xi=﹤x1，⋯，xi﹥即X序列的前i個字元(1≤i≤m)(Xi不妨讀作“字元串X的i字首”)

Yj=﹤y1，⋯，yj﹥即Y序列的前j個字元 (1≤j≤n)(字元串Y的j字首)；

LCS(X , Y) 為字元串X和Y的最長公共子序列，即為Z=﹤z1，⋯，zk﹥。

注：不嚴格的表述。事實上，X和Y的可能存在多個子串，長度相同并且最大，是以，LCS(X,Y)嚴格的說，是個字元串集合。即：Z∈ LCS(X , Y) .

LCS解法的探索：

若xm=yn(最後一個字元相同)，則：

Xm與Yn的最長公共子序列Zk的最後一個字元必定為xm

zk=xm=yn

LCS(Xm,Yn) = LCS(Xm-1,Yn-1)+xm

若xm≠yn，則：

LCS(Xm,Yn)= max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)}

算法中的資料結構：長度數組

使用二維數組C[m,n]

c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。

當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0

算法中的資料結構：方向變量

使用二維資料B[m,n]，其中，b[i,j]标記c[i,j]的值是由哪一個子問題的解達到的。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一個得到的。取值範圍為LeftTop ↖，Left ←，Top ↑ 三種情況

執行個體

X=< A，B，C，B，D，A，B >

Y=< B，D，C，A，B，A >

以上引用自七月線上

Pyhton代碼如下：

def LCS(s1, s2):
    size1 = len(s1) + 
    size2 = len(s2) + 
    # 程式多加一行，一列，友善後面代碼編寫
    chess = [[["", ] for j in list(range(size2))] for i in list(range(size1))]
    for i in list(range(, size1)):
        chess[i][][] = s1[i - ]
    for j in list(range(, size2)):
        chess[][j][] = s2[j - ]
    print("初始化資料：")
    print(chess)
    for i in list(range(, size1)):
        for j in list(range(, size2)):
            if s1[i - ] == s2[j - ]:
                chess[i][j] = ['↖', chess[i - ][j - ][] + ]
            elif chess[i][j - ][] > chess[i - ][j][]:
                chess[i][j] = ['←', chess[i][j - ][]]
            else:
                chess[i][j] = ['↑', chess[i - ][j][]]
    print("計算結果：")
    print(chess)
    i = size1 - 
    j = size2 - 
    s3 = []
    while i >  and j > :
        if chess[i][j][] == '↖':
            s3.append(chess[i][][])
            i -= 
            j -= 
        if chess[i][j][] == '←':
            j -= 
        if chess[i][j][] == '↑':
            i -= 
    s3.reverse()
    print("最長公共子序列：%s" % ''.join(s3))
           

調用：

輸出結果：

初始化資料：
[[['', 0], ['B', 0], ['D', 0], ['C', 0], ['A', 0], ['B', 0], ['A', 0]],
 [['A', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['C', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['D', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['A', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
 [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]]
計算結果：
[[['', 0], ['B', 0], ['D', 0], ['C', 0], ['A', 0], ['B', 0], ['A', 0]],
 [['A', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↖', 1], ['←', 1], ['↖', 1]],
 [['B', 0], ['↖', 1], ['←', 1], ['←', 1], ['↑', 1], ['↖', 2], ['←', 2]],
 [['C', 0], ['↑', 1], ['↑', 1], ['↖', 2], ['←', 2], ['↑', 2], ['↑', 2]],
 [['B', 0], ['↖', 1], ['↑', 1], ['↑', 2], ['↑', 2], ['↖', 3], ['←', 3]],
 [['D', 0], ['↑', 1], ['↖', 2], ['↑', 2], ['↑', 2], ['↑', 3], ['↑', 3]],
 [['A', 0], ['↑', 1], ['↑', 2], ['↑', 2], ['↖', 3], ['↑', 3], ['↖', 4]],
 [['B', 0], ['↖', 1], ['↑', 2], ['↑', 2], ['↑', 3], ['↖', 4], ['↑', 4]]]
最長公共子序列：BCBA