python实现:两个字符串‘abcdefhid’、'bdfgh'的最长相同有序串为‘bdfh’
时间: 2024-01-14 13:03:49 浏览: 23
可以使用动态规划来解决这个问题。首先,我们定义一个二维数组`dp`,其中`dp[i][j]`表示以字符串1的第`i`个字符和字符串2的第`j`个字符结尾的最长公共有序子串的长度。
然后,我们遍历字符串1和字符串2的所有字符,如果当前字符相同,则`dp[i][j]`等于`dp[i-1][j-1]`加1;否则,`dp[i][j]`等于0。
最后,我们找到`dp`数组中最大的值,以及对应的最后一个字符的位置,就可以得到最长公共有序子串。
下面是代码实现:
```python
def longest_common_subsequence(str1, str2):
n, m = len(str1), len(str2)
dp = [[0] * (m+1) for _ in range(n+1)]
max_len, end_pos = 0, 0
for i in range(1, n+1):
for j in range(1, m+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
return str1[end_pos-max_len:end_pos]
```
使用上面的代码,可以得到最长公共有序子串`bdfh`。