A和B的最長公共子序列是什么？LCS詳解

LCS是什么

【資料圖】

LCS是Longest Common Subsequence的縮寫，即最長公共子序列。一個序列，如果是兩個或者多個序列的子序列，并且是所有子序列中最長的，則為最長公共子序列。（有序但不連續也為子序列）

序列 13456 和 345674 的最長公共子序列為 3456序列 ABDBC 和 BCDBA 的最長公共子序列為 BDB

LCS可以用來做什么

生物學上用來進行基因序列比對，以推測序列的結構、功能和演化過程用來描述兩段文字的”相似性“，可以用來辨別是不是抄襲

怎么計算LCS

暴力窮舉法

就是把兩個序列所有的子序列都列出來，然后一一進行比較。

假定字符串 A 和 B 的長度分別為 n 和 m，那么 A 共有 2 n ? 1 2^n-1 2n?1 個子序列，B 共有 2 m ? 1 2^m-1 2m?1 個子序列，然后將任意兩個進行一一比較，最后得出 A 和 B 的最長公共子序列。這種算法的時間復雜度是 O ( 2 n + m ) O(2^{n+m}) O(2n+m) ，復雜度太高，當然不推薦使用。

動態規劃法

記：

字符串 A ，長度為 n ，從 1 開始；字符串 A ，長度為 n ，從 1 開始。

A i = < A 1 , A 2 , . . . A i > A_i=Ai=即 A 序列的前 i 個字符 ( 1 ≤ i ≤ n ) (1\leq i \leq n) (1≤i≤n) ( A i A_i Ai 計做”字符串 A 的 i 前綴)

B j = < B 1 , B 2 , . . . B j > B_j=Bj=即 B 序列的前 j 個字符 ( 1 ≤ j ≤ m ) (1\leq j \leq m) (1≤j≤m) ( B j B_j Bj 計做”字符串 B 的 j 前綴)

如果 A n = B m A_n=B_m An=Bm (最后一個字符相同)，那么 A 和 B 的最長公共子序列 C 的最后一位 C k = A n = B m C_k=A_n=B_m Ck=An=Bm ，那么 L C S ( A , B ) = L C S ( A n ? 1 , B m ? 1 ) + A n LCS(A,B)=LCS(A_n-1,B_m-1)+A_n LCS(A,B)=LCS(An?1,Bm?1)+An

如果 A n ? = B m A_n\not=B_m An?=Bm ，那么他們的最長公共子序列 C 要么是 L C S ( A n ? 1 , B m ) LCS(A_{n-1},B_m) LCS(An?1,Bm) ，要么是 L C S ( A n , B m ? 1 ) LCS(A_n,B_{m-1}) LCS(An,Bm?1) ，所以 L C S ( A , B ) = m a x { L C S ( A n ? 1 , B m ) , L C S ( A n , B m ? 1 ) } LCS(A,B)=max\{LCS(A_{n-1},B_m),LCS(A_n,B_{m-1})\} LCS(A,B)=max{LCS(An?1,Bm),LCS(An,Bm?1)}

1234567

ABDCABA

BABCBDAB

A 3 = B 3 = ′ C ′ A_3=B_3= "C" A3=B3=′C′ 那么 L C S ( B D C , A B C ) = L C S ( B D , A B ) + ′ C ′ LCS(BDC,ABC)=LCS(BD,AB)+"C" LCS(BDC,ABC)=LCS(BD,AB)+′C′

A 5 = B 4 = ′ B ′ A_5=B_4="B" A5=B4=′B′ 那么 L C S ( B D C A B , A B C B ) = L C S ( B D C A , A B C ) + ′ B ′ LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+"B" LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+′B′

A 2 ? = B 2 A_2\not=B_2 A2?=B2 那么 L C S ( B D , A B ) = m a x { L C S ( B , A B ) , L C S ( B D , A ) } LCS(BD,AB)=max\{LCS(B,AB),LCS(BD,A)\} LCS(BD,AB)=max{LCS(B,AB),LCS(BD,A)}

A 4 ? = B 5 A_4\not=B_5 A4?=B5 那么 L C S ( B D C A , A B C B D ) = m a x { L C S ( B D C , A B C B D ) , L C S ( B D C A , A B C B ) } LCS(BDCA,ABCBD)=max\{LCS(BDC,ABCBD),LCS(BDCA,ABCB)\} LCS(BDCA,ABCBD)=max{LCS(BDC,ABCBD),LCS(BDCA,ABCB)}

由以上可以得出

L C S ( A n , B m ) = { L C S ( A n ? 1 , B m ? 1 + A n )                          A n = B m m a x { L C S ( A n ? 1 , B m ) , L C S ( A n , B m ? 1 ) } A n ? = B m LCS(A_n,B_m)=\begin{cases}LCS(A_{n-1},B_{m-1}+A_n) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \quad A_n=B_m\\ max\{LCS(A_{n-1},B_m),LCS(A_n,B_{m-1})\} \quad A_n\not=B_m\end{cases} LCS(An,Bm)={LCS(An?1,Bm?1+An)                        An=Bmmax{LCS(An?1,Bm),LCS(An,Bm?1)}An?=Bm

使用動態規劃法求解

首先上一幅圖

記一個二維數組 c [ m , n ] c[m,n] c[m,n]， c [ i , j ] c[i,j] c[i,j] 的值為 x i x_i xi 和 y j y_j yj 的最長公共子序列的長度，然后不難得出當 i = 0 i=0 i=0 或 j = 0 j=0 j=0 的時候 X i X_i Xi 和 Y j Y_j Yj 的最長公共子序列的長度。然后通過動態規劃法的公式得出 c ( i , j ) = { 0 i = 0 , j = 0 c ( i ? 1 , j ? 1 )                          i > 0 , j > 0 , x i = y j m a x { c ( i ? 1 , j ) , c ( i , j ? 1 ) ) } i > 0 , j > 0 , x i ? = y j c(i,j)=\begin{cases}0 \quad \quad \quad \quad i=0,j=0 \\ c(i-1,j-1) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \quad i>0,j>0,x_i=y_j\\ max\{c(i-1,j),c(i,j-1))\} \quad i>0,j>0,x_i\not=y_j\end{cases} c(i,j)=?????0i=0,j=0c(i?1,j?1)                        i>0,j>0,xi=yjmax{c(i?1,j),c(i,j?1))}i>0,j>0,xi?=yj 然后我們通過公式計算 c ( 1 , 1 ) c(1,1) c(1,1) ，因為 x 1 x_1 x1 和 y 1 y_1 y1 不相等，得出 c ( 1 , 1 ) = m a x { c ( 0 , 1 ) , c ( 1 , 0 ) } = 0 c(1,1)=max \{ c(0,1),c(1,0) \}=0 c(1,1)=max{c(0,1),c(1,0)}=0 。然后依次計算，就會得到圖中的值，然后得出 x x x 和 y y y 的最長公共子序列的長度為4。我們在計算的時候會發現一個規律：當 x i = y j x_i=y_j xi=yj 的時候 c ( i , j ) c(i,j) c(i,j) 的值為左上角格子的數加1；當 x i ? = y j x_i\not=y_j xi?=yj 的時候 c ( i , j ) c(i,j) c(i,j) 的值為左側格子和上邊格子中的較大的一個。

代碼實現

import sysstr1 = sys.argv[1]str2 = sys.argv[2]len1 = len(str1)len2 = len(str2)maxChildLen = 0lcs_ss = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]for i in range(1, len1 + 1):    for j in range(1, len2 + 1):        if str1[i-1] == str2[j-1]:            lcs_ss[i][j] = lcs_ss[i-1][j-1] + 1        else:            lcs_ss[i][j] = max(lcs_ss[i-1][j], lcs_ss[i][j-1])maxChildLen = lcs_ss[len1][len2]print("str1: %s" % str1)print("str2: %s" % str2)print("LCS: %s" % maxChildLen)

隨便輸入兩個字符串，然后觀察打印結果

str1: acedbaestr2: becadeacLCS: 3Process finished with exit code 0

若有任何問題，懇請不吝指正。

歡迎關注公眾號：「努力給自己看」