最长公共子序列c++语言

最长公共子序列（Longest Common Subsequence, LCS）是指两个序列中最长的那个相同的子序列。在C++中，可以使用动态规划算法来解决这个问题。下面是一个基本的递归版和迭代版的解决方案：

**递归版本（时间复杂度较高）：**

int lcs(string str1, string str2, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    else if (str1[m - 1] == str2[n - 1])
        return 1 + lcs(str1, str2, m - 1, n - 1);
    else
        return max(lcs(str1, str2, m, n - 1), lcs(str1, str2, m - 1, n));
}

**迭代版本（空间效率更高）：**

vector<vector<int>> dp(int m, int n) {
    vector<vector<int>> lcs_table(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (str1[i - 1] == str2[j - 1]) {
                lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1;
            } else {
                lcs_table[i][j] = max(lcs_table[i - 1][j], lcs_table[i][j - 1]);
            }
        }
    }

    return lcs_table[m][n];
}

string findLCS(string str1, string str2) {
    int length = dp(str1.length(), str2.length());
    char result[length + 1];
    result[length] = '\0';

    // 从右下角开始回溯构建LCS
    int i = str1.length(), j = str2.length();
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            result[length - 1] = str1[i - 1];
            i--;
            j--;
            length--;
        } else if (lcs_table[i - 1][j] > lcs_table[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result;
}