最长公共子序列的py代码
时间: 2024-06-17 20:05:34 浏览: 62
最长公共子序列(Longest Common Subsequence,LCS)是指给定两个序列X和Y,找出一个它们的最长公共子序列。
以下是一个简单的Python代码实现:
```python
def lcs(x, y):
m = len(x)
n = len(y)
# 创建二维数组记录状态转移信息
c = [ * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i - 1][j], c[i][j - 1])
# 回溯查找LCS
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if x[i - 1] == y[j - 1]:
lcs = x[i - 1] + lcs
i -= 1
j -= 1
elif c[i - 1][j] > c[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
```
其中,`x`和`y`分别为两个字符串,`m`和`n`为它们的长度。在函数中,我们创建了一个二维数组`c`来记录状态转移信息,并利用动态规划的思想,从左上角开始逐行逐列地计算每个格子的值。当两个字符相等时,当前位置的值等于左上角位置的值加一;否则,当前位置的值等于左边位置和上边位置中较大的一个。
最后,我们通过回溯查找LCS。具体来说,从右下角开始,如果两个字符相等,则将该字符添加到LCS中,并向左上角移动;否则,如果上方的值大于左侧的值,则向上移动;否则,向左移动。