LCS详解

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

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

---

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

二维码