LCS是什么

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

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

LCS可以用來做什么

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

怎么計算LCS

• 暴力窮舉法

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

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

• 動態規劃法

  記：

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

  $A_i=<A_1,A_2,...Ai>$ 即 A 序列的前 i 個字符 $(1\le i\le n)$ ($A_i$ 計做”字符串 A 的 i 前綴)

  $B_j=<B_1,B_2,...Bj>$ 即 B 序列的前 j 個字符 $(1\le j\le m)$ ($B_j$ 計做”字符串 B 的 j 前綴)

  如果 $A_n=B_m$ (最后一個字符相同)，那么 A 和 B 的最長公共子序列 C 的最后一位 $C_k=A_n=B_m$ ，那么 $LCS(A,B)=LCS(A_n?1,B_m?1)+A_n$

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

  1234567

  A	B	D	C	A	B	A
  B	A	B	C	B	D	A	B

  $A_3=B_3{=}^{\prime }{C}^{\prime }$ 那么 $LCS(BDC,ABC)=LCS(BD,AB){+}^{\prime }{C}^{\prime }$

  $A_5=B_4{=}^{\prime }{B}^{\prime }$ 那么 $LCS(BDCAB,ABCB)=LCS(BDCA,ABC){+}^{\prime }{B}^{\prime }$

  $A_2?=B_2$ 那么 $LCS(BD,AB)=max\{LCS(B,AB),LCS(BD,A)\}$

  $A_4?=B_5$ 那么 $LCS(BDCA,ABCBD)=max\{LCS(BDC,ABCBD),LCS(BDCA,ABCB)\}$

  由以上可以得出

  $$LCS(A_n,B_m)=\{\begin{array}{l}LCS(A_{n?1},B_{m?1}+A_n)A_n=B_m\\ max\{LCS(A_{n?1},B_m),LCS(A_n,B_{m?1})\}{A}_n?=B_m\end{array}$$

使用動態規劃法求解

首先上一幅圖

記一個二維數組 $c[m,n]$，$c[i,j]$ 的值為 $x_i$ 和 $y_j$ 的最長公共子序列的長度，然后不難得出當 $i=0$ 或 $j=0$ 的時候 $X_i$ 和 $Y_j$ 的最長公共子序列的長度。然后通過動態規劃法的公式得出
$$c(i,j)=?\begin{array}{l}0i=0,j=0\\ c(i?1,j?1)i>0,j>0,x_i=y_j\\ max\{c(i?1,j),c(i,j?1))\}i>0,j>0,x_i?=y_j\end{array}$$
然后我們通過公式計算 $c(1,1)$ ，因為 $x_1$ 和 $y_1$ 不相等，得出 $c(1,1)=max\{c(0,1),c(1,0)\}=0$ 。然后依次計算，就會得到圖中的值，然后得出 $x$ 和 $y$ 的最長公共子序列的長度為4。我們在計算的時候會發現一個規律：當 $x_i=y_j$ 的時候 $c(i,j)$ 的值為左上角格子的數加1；當 $x_i?=y_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] + 1else: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: acedbae str2: becadeac LCS: 3Process finished with exit code 0

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

---

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

總結

以上是生活随笔為你收集整理的LCS详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。