1、最长公共子序列 设:a[0:n-1]和b[0:m-1]是两个字符串数组,由’abcdef’中的字符组成, a[]=”acdfecdfbb”; b[]=”bcdfaedfbc” 1)请实现找a,b的最长公共子序列算法。
时间: 2023-06-07 21:08:01 浏览: 109
好的,这是一个计算问题,可以提供详细的解答。最长公共子序列的问题可以采用动态规划算法来解决。我们可以建立一个二维数组dp[i][j],其中dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列长度。那么动态规划的转移方程如下:
1. 当a[i] == b[j]时, dp[i][j] = dp[i-1][j-1] + 1
2. 当a[i] != b[j]时, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
最后dp[n-1][m-1]即为a和b的最长公共子序列长度。接下来可以用回溯法来找到最长公共子序列的具体内容。
相关问题
最长公共子序列 设:a[0:n-1]和b[0:m-1]是两个字符串数组,由’abcdef’中的字符组成, a[]=”acdfecdfbb”; b[]=”bcdfaedfbc” 1)请实现找a,b的最长公共子序列算法。 2)实现空间优化的最长子序列算法。
1)找a,b的最长公共子序列算法:
我们可以使用动态规划的思想来解决这个问题。
首先,我们定义一个二维数组dp,其中dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列的长度。
然后,我们可以根据以下两种情况来求解dp[i][j]:
1. 如果a[i] == b[j],那么dp[i][j] = dp[i-1][j-1] + 1;
2. 如果a[i] != b[j],那么dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
最终,dp[n-1][m-1]就是a和b的最长公共子序列的长度。
不过,这种算法只能求出最长公共子序列的长度,而不能求出具体的最长公共子序列。
2)空间优化的最长子序列算法:
在上面的算法中,我们使用了一个二维数组来保存状态,因此空间复杂度为O(nm)。但实际上,我们只需要用到dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]这三个状态,因此可以将二维数组优化为一维数组。
具体地,我们可以定义一个一维数组dp,其中dp[j]表示a[0:i]和b[0:j]的最长公共子序列的长度。在每次更新dp[j]时,我们需要用到之前的dp[j-1]、dp[j]和dp[j-1]这三个状态。因此,我们可以用一个变量pre来保存dp[j-1]的值,用一个变量cur来保存dp[j]的值,用一个变量tmp来保存dp[j-1]的值。在更新dp[j]时,我们先将pre赋值给tmp,然后将cur更新为max(tmp, dp[j]),最后再将cur赋值给pre。这样,我们就可以用O(min(n,m))的空间复杂度来求解最长公共子序列的长度了。
最长公共子序列问题:给定两个字符串,求它们的最长公共子序列
最长公共子序列问题可以通过动态规划算法来解决。
定义一个二维数组 dp,其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列的长度。
状态转移方程如下:
当 s1[i-1] == s2[j-1] 时,说明当前字符可以作为最长公共子序列的一部分,因此 dp[i][j] = dp[i-1][j-1] + 1。
当 s1[i-1] != s2[j-1] 时,说明当前字符不能作为最长公共子序列的一部分,因此需要去掉 s1 的最后一个字符或者去掉 s2 的最后一个字符,取它们的最大值,即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终结果为 dp[m][n],其中 m 和 n 分别为字符串 s1 和 s2 的长度。
以下是 Python 代码实现:
```
def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ 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]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
```
例如,对于字符串 s1 = "abcde" 和 s2 = "ace",最长公共子序列为 "ace",长度为 3。