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

若有任何问题，恳请不吝指正。

欢迎关注公众号：「努力给自己看」