c++如何根据最长公共子序列长度得到子序列，请输出代码

在C++中，可以使用动态规划的方法来计算两个字符串的最长公共子序列（LCS，Longest Common Subsequence）并找到最长的子序列。以下是经典的Hunt–Szymanski算法的一个实现：

#include <iostream>
#include <vector>

std::string findLCS(std::string str1, std::string str2) {
    int m = str1.length();
    int n = str2.length();

    // 初始化二维动态规划数组
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 递推过程填充dp表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 从右下角回溯构建LCS
    std::string lcs = "";
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1]) {
            lcs += str1[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

int main() {
    std::string str1 = "ABCBDAB";
    std::string str2 = "BDCAB";
    std::cout << "Longest Common Subsequence: " << findLCS(str1, str2) << std::endl;

    return 0;
}

这个程序首先初始化一个二维数组`dp`，然后通过遍历两个输入字符串，根据字符是否相等更新`dp`数组。最后，从`dp`数组的右下角开始回溯，构造出最长公共子序列。