LCS是什么
LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或者多个序列的子序列，并且是所有子序列中最长的，则为最长公共子序列。（有序但不连续也为子序列）
- 序列 13456 和 345674 的最长公共子序列为 3456
- 序列 ABDBC 和 BCDBA 的最长公共子序列为 BDB
LCS可以用来做什么
- 生物学上用来进行基因序列比对，以推测序列的结构、功能和演化过程
- 用来描述两段文字的”相似性“，可以用来辨别是不是抄袭
怎么计算LCS
-
暴力穷举法
就是把两个序列所有的子序列都列出来，然后一一进行比较。
假定字符串 A 和 B 的长度分别为 n 和 m，那么 A 共有
个子序列，B 共有
个子序列，然后将任意两个进行一一比较，最后得出 A 和 B 的最长公共子序列。这种算法的时间复杂度是
，复杂度太高，当然不推荐使用。
-
动态规划法
记：
字符串 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 那么
那么
那么
那么
由以上可以得出
使用动态规划法求解
首先上一幅图
0_1313577405FsRn.gif
记一个二维数组 ，
的值为
和
的最长公共子序列的长度，然后不难得出当
或
的时候
和
的最长公共子序列的长度。然后通过动态规划法的公式得出
然后我们通过公式计算 ，因为
和
不相等，得出
。然后依次计算，就会得到图中的值，然后得出
和
的最长公共子序列的长度为4。我们在计算的时候会发现一个规律：当
的时候
的值为左上角格子的数加1；当
的时候
的值为左侧格子和上边格子中的较大的一个。
代码实现
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)
随便输入两个字符串，然后观察打印结果
str1: acedbae
str2: becadeac
LCS: 3
Process finished with exit code 0
若有任何问题，恳请不吝指正。
欢迎关注公众号：「努力给自己看」
二维码
