python查找公共子序列
时间: 2023-06-28 16:06:44 浏览: 53
可以使用动态规划算法来查找公共子序列,以下是Python代码示例:
```python
def lcs(X, Y):
# 获取字符串长度
m = len(X)
n = len(Y)
# 初始化一个二维数组来保存公共子序列的长度
lcs_table = [[0] * (n + 1) for i in range(m + 1)]
# 填充lcs_table,计算公共子序列的长度
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
lcs_table[i][j] = lcs_table[i-1][j-1] + 1
else:
lcs_table[i][j] = max(lcs_table[i-1][j], lcs_table[i][j-1])
# 从lcs_table中获取最长公共子序列的值
index = lcs_table[m][n]
lcs = [''] * index
i = m
j = n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i -= 1
j -= 1
index -= 1
elif lcs_table[i-1][j] > lcs_table[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(lcs)
```
这个函数接受两个字符串作为参数,返回它们之间的最长公共子序列。