最长公共子序列长度python
时间: 2023-11-15 10:03:32 浏览: 49
最长公共子序列长度可以使用动态规划算法来解决。具体来说,可以使用一个二维数组来记录两个字符串的最长公共子序列长度。如果两个字符串的最后一个字符相同,则最长公共子序列长度为它们去掉最后一个字符后的最长公共子序列长度加1;否则,最长公共子序列长度为它们去掉一个字符后的最长公共子序列长度的最大值。最终,二维数组右下角的元素即为两个字符串的最长公共子序列长度。
根据提供的引用,可以使用以下代码来求解最长公共子序列长度:
n, m = map(int, input().split())
s1 = ' ' + input()
s2 = ' ' + input()
ans = [ * (m + 1) for i in range(0, n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i] == s2[j]:
ans[i][j] = ans[i - 1][j - 1] + 1
else:
ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
print(ans[n][m])
根据提供的引用,最长公共子序列长度为4。
相关问题
最长公共子序列问题 python
最长公共子序列问题是指,给定两个序列,找到它们之间最长的公共子序列。子序列指的是从原序列中删除任意个元素后得到的新序列。因此,最长公共子序列问题就是要在两个给定序列中找到一个最长的子序列,使得这个子序列在两个原序列中都存在。
在Python中,可以使用动态规划算法来解决最长公共子序列问题。具体来说,可以定义一个二维数组dp,其中dp[i][j]表示第一个序列中前i个元素和第二个序列中前j个元素之间的最长公共子序列长度。然后可以根据以下递推关系来计算dp[i][j]:
1. 当第一个序列的第i个元素和第二个序列的第j个元素相同时,dp[i][j] = dp[i-1][j-1] + 1;
2. 当第一个序列的第i个元素和第二个序列的第j个元素不同时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终,最长公共子序列的长度为dp[-1][-1]。同时,可以根据dp数组还原出最长公共子序列本身。
最长公共子序列的python代码
最长公共子序列(Longest Common Subsequence)是指在两个序列中都出现过的最长的子序列。以下是一个Python实现:
```python
def longest_common_subsequence(str1, str2):
len1 = len(str1)
len2 = len(str2)
dp = [ * (len2+1) for _ in range(len1+1)]
for i in range(1, len1+1):
for j in range(1, len2+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[len1][len2]
```
其中,dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。如果str1[i-1]等于str2[j-1],则说明它们都在最长公共子序列中,所以dp[i][j]等于dp[i-1][j-1]中的较大值。
相关推荐
![text/x-c](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)