求两个字符串的最长公共子序列的长度. 输入:第一行字符串S1,第二行字符串 S2 (1<=字符串长度<=1000).输出:数字M,为最长公共子序列长度.测试用例如下: 输入 BDCABA ABCBDAB 输出 4 BCBA BCAB BDAB编写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个字符串的最长公共子序列和最长公共子字符串...

好的，针对你的问题，我来给你解答。

首先，最长公共子序列（Longest Common Subsequence，简称 LCS）指的是给定两个字符串，找到它们之间最长的公共子序列的长度。而最长公共子字符串（Longest Common Substring，简称 LPS）指的是给定两个字符串，找到它们之间最长的公共子字符串。

接下来，我分别介绍如何求解这两个问题。

1. 最长公共子序列（LCS）

求解最长公共子序列的问题可以使用动态规划的思想来解决。具体的，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示第一个字符串的前 i 个字符和第二个字符串的前 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 分别为两个字符串的长度。

同时，我们可以通过倒推 dp 数组，求出最长公共子序列具体是哪些字符。

2. 最长公共子字符串（LPS）

求解最长公共子字符串的问题也可以使用动态规划的思想来解决。具体的，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示以第一个字符串的第 i 个字符和第二个字符串的第 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 分别为最长公共子字符串在两个字符串中的结尾位置。

同时，我们也可以通过倒推 dp 数组，求出最长公共子字符串具体是哪些字符。

希望我的回答能够帮助到你。

给定两个字符串，寻找这两个字串之间的最长公共子序列。 输入格式：输入两行，分别包含一个字符串，仅含有小写字母。 输出格式：最长公共子序列的长度。

非常感谢您的提问！这是一个经典的动态规划问题。以下是代码实现：

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))

如果您有任何其他问题，请随时问我。