C++实现长公共子序列长度 分数 15 作者 王东 单位 贵州师范学院 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。

下面是C++的参考代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int dp[N][N];

int main()
{
    string A, B;
    cin >> A >> B;

    int m = A.size(), n = B.size();

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }

    cout << dp[m][n] << endl;

    return 0;
}

其中，使用dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。对于状态转移方程，需要特别注意字符串下标从0开始，因此需要将i和j减1。

相关问题

c++贪心算法解决最长公共子序列长度问题，求两个字符串的最长公共子序列长度

最长公共子序列（Longest Common Subsequence，LCS）问题是一类经典的字符串匹配问题，它的解决方法可以使用动态规划或贪心算法。

下面是使用贪心算法解决最长公共子序列长度问题的思路：

1. 对于两个字符串s1和s2，从两个字符串的开头开始扫描。

2. 如果当前字符相同，那么将两个字符串都向后移动一个字符，即i=i+1，j=j+1。

3. 如果当前字符不同，那么需要考虑哪个字符串的当前字符可以被舍弃，从而尽可能找到更多的共同字符。这里采用的是贪心策略，即选择当前字符匹配次数较多的字符串的当前字符，将其舍弃。

4. 最后，计算出舍弃的字符数，即为最长公共子序列长度。

下面是C++代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1010;

int f[N][N];

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (s1[i - 1] == s2[j - 1])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;

    return 0;
}

其中，f[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度。状态转移方程为：

f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]+(s1[i-1]==s2[j-1]))

时间复杂度为O(nm)，空间复杂度为O(nm)。

用c++写一个求两个字符串最长公共子序列的长度和字符的程序

好的，以下是代码：

#include <stdio.h>
#include <string.h>
#define MAX_LEN 100

int lcs[MAX_LEN+1][MAX_LEN+1];

int main() {
    char str1[MAX_LEN], str2[MAX_LEN];
    printf("请输入两个字符串（以空格分隔）：\n");
    scanf("%s%s", str1, str2);

    int len1 = strlen(str1), len2 = strlen(str2);
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[j-1]) {
                lcs[i][j] = lcs[i-1][j-1] + 1;
            }
            else {
                lcs[i][j] = (lcs[i-1][j] > lcs[i][j-1]) ? lcs[i-1][j] : lcs[i][j-1];
            }
        }
    }

    printf("最长公共子序列长度为：%d\n", lcs[len1][len2]);

    printf("最长公共子序列为：");
    int i = len1, j = len2;
    char lcs_str[MAX_LEN];
    int idx = 0;
    while (i && j) {
        if (str1[i-1] == str2[j-1]) {
            lcs_str[idx++] = str1[i-1];
            i--;
            j--;
        }
        else {
            if (lcs[i-1][j] > lcs[i][j-1]) {
                i--;
            }
            else {
                j--;
            }
        }
    }

    for (int i = idx-1; i >= 0; i--) {
        printf("%c", lcs_str[i]);
    }
    printf("\n");
    
    return 0;
}

希望对你有帮助啊！

还有一个笑话，为什么大象不会使用电脑？因为它的鼠标跑不动！