用c++编写最长公共子序列

在 C++ 中，计算两个字符串的最长公共子序列（Longest Common Subsequence, LCS）通常使用动态规划算法来解决。这里是一个基本的递归版和迭代版的实现方法：

**递归版本：**

#include <string>
using namespace std;

int lcsRec(string X, string Y, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    else if (X[m - 1] == Y[n - 1])
        return 1 + lcsRec(X, Y, m - 1, n - 1);
    else
        return max(lcsRec(X, Y, m, n - 1), lcsRec(X, Y, m - 1, n));
}

// 获取最长公共子序列的长度
string getLCS(string X, string Y) {
    int m = X.size(), n = Y.size();
    return lcsRec(X, Y, m, n);
}

**迭代版本（更常见用于实际项目）：**

#include <vector>
using namespace std;

int lcsIterative(string X, string Y, vector<vector<int>>& dp) {
    int m = X.length(), n = Y.length();

    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[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];
}

// 返回最长公共子序列长度并打印
string getLCS(string X, string Y) {
    int m = X.length(), n = Y.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    int len = lcsIterative(X, Y, dp);

    // 重建最长公共子序列
    string result(len, ' ');
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            result[len - 1] = X[i - 1];
            i--;
            j--;
            len--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return result;
}

这两个版本都可以找到给定字符串 X 和 Y 的最长公共子序列。