编程要求 求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列 解题思路: 递推关系分析: 设 A=“a0,a1,…,am−1”,B=“b0,b1,…,bn−1”,Z=“z0,z1,…,zk−1” 为它们的最长公共子序列。 有以下结论: 1)如果am−1=bn−1,则zk−1=am−1=bn−1,且“z0,z1,…,zk−2”是“a0,a1,…,am−2”和“b0,b1,…,bn−2”的一个最长公共子序列; 2)如果am−1=bn−1,则若zk−1=am−1,蕴涵“z0,z1,…,zk−1”是“a0,a1,…,am−2”和“b0,b1,…,bn−1”的一个最长公共子序列; 3)如果am−1=bn−1,则若zk−1=bn−1,蕴涵“z0,z1,…,zk−1”是“a0,a1,…,am−1”和“b0,b1,…,bn−2”的一个最长公共子序列。 定义c[i][j]为序列“a0,a1,…,ai−1”和“b0,b1,…,bj−1”的最长公共子序列的长度,计算c[i][j]可递归地表述如下: 1)c[i][j]=0 如果i=0或j=0; 2)c[i][j]=c[i−1][j−1]+1 如果i,j>0,且a[i−1]=b[j−1]; 3)c[i][j]=max(c[i][j−1],c[i−1][j]) 如果i,j>0,且a[i−1]=b[j−1]。 由二维数组c的递归定义,c[i][j]的结果依赖于c[i−1][j−1],c[i−1][j]和c[i][j−1]。可以从c[m][n]开始,跟踪c[i][j]结果的产生过程,从而逆向构造出最长公共子序列。 测试说明 平台会对你编写的代码进行测试: 测试输入: a=“ABCDBAB” b=“BDCABA” 输出示例: BCBA
时间: 2024-01-01 19:04:36 浏览: 55
以下是Python代码实现:
```python
def lcs(a, b):
m, n = len(a), len(b)
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 a[i-1] == b[j-1]:
c[i][j] = c[i-1][j-1] + 1
else:
c[i][j] = max(c[i][j-1], c[i-1][j])
res = ""
i, j = m, n
while i > 0 and j > 0:
if a[i-1] == b[j-1]:
res = a[i-1] + res
i -= 1
j -= 1
elif c[i-1][j] > c[i][j-1]:
i -= 1
else:
j -= 1
return res
a = "ABCDBAB"
b = "BDCABA"
print(lcs(a, b)) # output: BCBA
```
相关问题
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
使用动态规划算法可以求解两个字符串的最长公共子序列。
设字符串A为"ABCDBAB",字符串B为"BDCABA",用dp[i][j]表示A的前i个字符和B的前j个字符的最长公共子序列长度,则有以下递推式:
- 当A[i] == B[j]时,dp[i][j] = dp[i-1][j-1] + 1
- 当A[i] != B[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])
根据递推式,可以使用二维数组dp来保存每个子问题的结果。最终的答案就是dp[A.length()][B.length()]。下面是具体的代码实现:
```
public static String longestCommonSubsequence(String A, String B) {
int[][] dp = new int[A.length() + 1][B.length() + 1];
for (int i = 1; i <= A.length(); i++) {
for (int j = 1; j <= B.length(); j++) {
if (A.charAt(i-1) == B.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
int i = A.length(), j = B.length();
StringBuilder sb = new StringBuilder();
while (i > 0 && j > 0) {
if (A.charAt(i-1) == B.charAt(j-1)) {
sb.append(A.charAt(i-1));
i--;
j--;
} else {
if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
}
return sb.reverse().toString();
}
```
使用该函数可以得到字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列为“BDAB”。
用c语言求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
这是一个经典的问题,有多种解决方法。一种常见的方法是使用动态规划算法。
具体来说,我们可以定义一个二维数组L,其中L[i][j]表示字符串序列1的前i个字符与字符串序列2的前j个字符的最长公共子序列长度。然后,我们可以按照以下递推式来计算L数组的值:
L[i][j] = 0 (i = 0 或 j = 0)
L[i][j] = L[i-1][j-1] + 1 (sequence1[i] = sequence2[j])
L[i][j] = max(L[i][j-1], L[i-1][j]) (sequence1[i] != sequence2[j])
最终,L[m][n]就是要求的最长公共子序列长度,其中m和n分别是两个字符串序列的长度。我们可以根据L数组求出最长公共子序列本身。
在这个例子中,当使用动态规划算法时,得到的最长公共子序列是“BDAB”,长度为4。