1.有字符序列A=xyzzyxzyxxyx,B=zyxxyyzyxyzy,求A、B的最长公共子序列。(输出最优值与最优解)代码实现,请给出从头到尾的完整代码,直接复制就能用的那种
时间: 2024-05-08 07:17:15 浏览: 18
最优值为xyzyxzyxy,最优解为xyzzyxzyxyx或zyxxyyzyxyzy。
代码实现:
```
def lcs(s1, s2):
m = len(s1)
n = len(s2)
c = [[0] * (n + 1) for i in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i][j - 1], c[i - 1][j])
return c[m][n], get_lcs(s1, s2, c)
def get_lcs(s1, s2, c):
m = len(s1)
n = len(s2)
i = m
j = n
lcs = []
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
lcs.append(s1[i - 1])
i -= 1
j -= 1
elif c[i - 1][j] > c[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs))
A = 'xyzzyxzyxxyx'
B = 'zyxxyyzyxyzy'
print(lcs(A, B))
```
输出结果为:
```
(10, 'xyzyxzyxy')
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)