用c++求两个字符串的最长公共子序列

好的，这是一道算法问题。可以使用动态规划算法来解决。具体方法是，定义一个二维数组dp，dp[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符的最长公共子序列的长度。然后根据最后一个字符是否相等来更新dp数组，最后返回dp[m][n]即可，其中m和n分别表示两个字符串的长度。需要注意的是，如果两个字符串中有一个为空串，那么最长公共子序列为0。

相关问题

用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;
}

希望对你有帮助啊！

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

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。