求两个字符串的最长公共子序列的长度. 输入:第一行字符串S1,第二行字符串 S2 (1<=字符串长度<=1000).输出:数字M,为最长公共子序列长度.测试用例如下: 输入 BDCABA ABCBDAB 输出 4 BCBA BCAB BDAB编写C语言代码
时间: 2024-02-17 17:04:08 浏览: 79
好的,这里是 C 语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define N 1010
int dp[N][N];
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
char s1[N], s2[N];
scanf("%s", s1);
scanf("%s", s2);
int n = strlen(s1), m = strlen(s2);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
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]);
}
printf("%d\n", dp[n][m]);
return 0;
}
```
这里同样采用了动态规划思想,使用一个二维数组 dp 存储最长公共子序列的长度。
时间复杂度为 O(nm)。
相关问题
两个字符串的最长公共子序列长度_求2个字符串的最长公共子序列和最长公共子字符串...
好的,我来回答你的问题。
两个字符串的最长公共子序列长度可以使用动态规划算法来求解。具体的实现方法是,定义一个二维数组 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],则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终的结果就是 dp[m][n],其中 m 和 n 分别是字符串 s1 和 s2 的长度。
最长公共子字符串的求解也可以使用动态规划算法。定义一个二维数组 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],则 dp[i][j] = 0。
最终的结果就是 dp[i][j] 中的最大值,其中 i 和 j 分别是字符串 s1 和 s2 的长度。
希望我的回答能够帮到你!
给定两个字符串,寻找这两个字串之间的最长公共子序列。 输入格式:输入两行,分别包含一个字符串,仅含有小写字母。 输出格式:最长公共子序列的长度。
非常感谢您的提问!这是一个经典的动态规划问题。以下是代码实现:
```python
def lcs(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 = input()
s2 = input()
print(lcs(s1, s2))
```
如果您有任何其他问题,请随时问我。
阅读全文
相关推荐












