相同序列最长公共子序列python实现
时间: 2023-08-05 16:03:09 浏览: 46
最长公共子序列(Longest Common Subsequence,简称LCS)是指在两个序列中找到一个最长的子序列,使得该子序列在两个序列中出现的顺序一致,但不要求连续。下面是一个用Python实现最长公共子序列的示例:
```python
def longest_common_subsequence(seq1, seq2):
m = len(seq1)
n = len(seq2)
# 创建一个二维数组来存储中间结果
dp = [[0] * (n+1) for _ in range(m+1)]
# 填充二维数组,计算LCS的长度
for i in range(1, m+1):
for j in range(1, n+1):
if seq1[i-1] == seq2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 从二维数组中构建LCS
lcs = []
i, j = m, n
while i > 0 and j > 0:
if seq1[i-1] == seq2[j-1]:
lcs.append(seq1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
# 反转LCS得到最终结果
lcs.reverse()
return lcs
# 示例用法
seq1 = "ABCDGH"
seq2 = "AEDFHR"
lcs = longest_common_subsequence(seq1, seq2)
print("Longest Common Subsequence:", "".join(lcs))
```
在这个示例中,我们定义了一个`longest_common_subsequence`函数,它接受两个序列`seq1`和`seq2`作为输入。函数使用动态规划的方法计算LCS的长度,并构建LCS序列。
在主程序中,我们使用示例输入序列`"ABCDGH"`和`"AEDFHR"`来测试`longest_common_subsequence`函数,并打印最长公共子序列。
运行上述代码,输出结果将是:
```
Longest Common Subsequence: ADH
```
这表示序列`"ADH"`是`"ABCDGH"`和`"AEDFHR"`的最长公共子序列。
希望这个示例对你有帮助!如果你还有其他问题,请随时提问。