LCS是什么
LCS是Longest Common Subsequence的縮寫，即最長公共子序列。一個序列，如果是兩個或者多個序列的子序列，并且是所有子序列中最長的，則為最長公共子序列。（有序但不連續(xù)也為子序列）
- 序列 13456 和 345674 的最長公共子序列為 3456
- 序列 ABDBC 和 BCDBA 的最長公共子序列為 BDB
LCS可以用來做什么
- 生物學上用來進行基因序列比對，以推測序列的結(jié)構(gòu)、功能和演化過程
- 用來描述兩段文字的”相似性“，可以用來辨別是不是抄襲
怎么計算LCS
-
暴力窮舉法
就是把兩個序列所有的子序列都列出來，然后一一進行比較。
假定字符串 A 和 B 的長度分別為 n 和 m，那么 A 共有
個子序列，B 共有
個子序列，然后將任意兩個進行一一比較，最后得出 A 和 B 的最長公共子序列。這種算法的時間復雜度是
，復雜度太高，當然不推薦使用。
-
動態(tài)規(guī)劃法
記：
字符串 A ，長度為 n ，從 1 開始；字符串 A ，長度為 n ，從 1 開始。
即 A 序列的前 i 個字符
(
計做”字符串 A 的 i 前綴)
即 B 序列的前 j 個字符
(
計做”字符串 B 的 j 前綴)
如果
(最后一個字符相同)，那么 A 和 B 的最長公共子序列 C 的最后一位
，那么
如果
，那么他們的最長公共子序列 C 要么是
，要么是
，所以
1 2 3 4 5 6 7 A B D C A B A B A B C B D A B 那么
那么
那么
那么
由以上可以得出
使用動態(tài)規(guī)劃法求解
首先上一幅圖
記一個二維數(shù)組 ，
的值為
和
的最長公共子序列的長度，然后不難得出當
或
的時候
和
的最長公共子序列的長度。然后通過動態(tài)規(guī)劃法的公式得出
然后我們通過公式計算 ，因為
和
不相等，得出
。然后依次計算，就會得到圖中的值，然后得出
和
的最長公共子序列的長度為4。我們在計算的時候會發(fā)現(xiàn)一個規(guī)律：當
的時候
的值為左上角格子的數(shù)加1；當
的時候
的值為左側(cè)格子和上邊格子中的較大的一個。
代碼實現(xiàn)
import sys
str1 = sys.argv[1]
str2 = sys.argv[2]
len1 = len(str1)
len2 = len(str2)
maxChildLen = 0
lcs_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)
隨便輸入兩個字符串，然后觀察打印結(jié)果
str1: acedbae
str2: becadeac
LCS: 3
Process finished with exit code 0
若有任何問題，懇請不吝指正。
歡迎關(guān)注公眾號：「努力給自己看」
