lcs最长公共子序列
时间: 2023-11-25 13:49:09 浏览: 33
LCS是最长公共子序列(Longest common subsequence problem)的缩写。LCS问题是在一组序列(通常只有两个序列)中找到所有序列共有的最长子序列的问题。它与最长公共子串问题不同:与子串不同,子序列不需要占据原始序列中的连续位置。最长公共子序列问题是经典的计算机科学问题,是 diff 实用程序等数据比较程序的基础,在计算语言学和生物信息学中有应用。它还被 Git 等版本控制系统广泛用于协调对受版本控制的文件集合所做的多项更改。
举个例子,假设有两个序列 A 和 B,它们分别为 A={A,B,C,B,D,A,B} 和 B={B,D,C,A,B,A},那么它们的最长公共子序列为{B,C,B,A},长度为4。
相关问题
python最长公共子序列lcs
Python中最长公共子序列(LCS)问题是求两个字符串最长公共子序列的问题。最长公共子序列是指两个字符串中都存在的最长的子序列(不要求连续)。解法是使用动态规划,用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子序列的位置。
下面是一个Python实现的例子:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n], dp
str1 = "abcba"
str2 = "bdcaba"
length, dp = lcs(str1, str2)
print("最长公共子序列长度为:", length)
print("dp表为:", dp)
```
运行结果:
```
最长公共子序列长度为: 4
dp表为: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 2, 2], [0, 0, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 3], [0, 1, 2, 2, 3, 3, 3], [0, 1, 2, 2, 3, 3, 4]]
最长公共子序列为: bcba
```
最长公共子序列问题lcs
最长公共子序列问题(LCS)是指给定两个字符串,求它们的最长公共子序列。子序列是指从原序列中删除一些字符(不一定连续)后得到的新序列,并且新序列中字符的相对位置与原序列中的相对位置相同。最长公共子序列是指在所有的公共子序列中最长的那一个。与最长公共子串问题不同的是,最长公共子序列问题不要求子序列连续。