用c++写给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，求所有最长公共子序列。

这个问题可以使用动态规划算法来解决，具体步骤如下：

1. 定义一个二维数组 dp，其中 dp[i][j] 表示序列 X 中前 i 个元素与序列 Y 中前 j 个元素的最长公共子序列的长度。

2. 初始化 dp[0][j] 和 dp[i][0] 均为 0，因为其中一个序列为空时，它们的最长公共子序列的长度必然为 0。

3. 对于任意的 i 和 j，如果 xi = yj，则 dp[i][j] = dp[i-1][j-1] + 1，因为此时两个序列的最后一个元素相同，所以它们的最长公共子序列长度加 1。

4. 如果 xi ≠ yj，则 dp[i][j] 的值等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值，即：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

5. 最终，dp[m][n] 即为序列 X 和 Y 的最长公共子序列的长度。

6. 通过回溯找出最长公共子序列。从 dp[m][n] 开始，如果 xi = yj，则将 xi 加入结果序列中，同时将 i 和 j 均减 1；否则，如果 dp[i-1][j] > dp[i][j-1]，则将 i 减 1；否则将 j 减 1。重复以上步骤，直到 i = 0 或 j = 0。

C++ 代码实现如下：

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

vector<vector<int>> dp;  // 二维数组 dp
vector<int> X, Y;  // 两个序列

void LCS(int i, int j, vector<int>& res) {
    if (i == 0 || j == 0) return;  // 递归结束条件
    if (X[i-1] == Y[j-1]) {  // 如果 xi = yj
        LCS(i-1, j-1, res);
        res.push_back(X[i-1]);  // 将 xi 加入结果序列中
    } else if (dp[i-1][j] > dp[i][j-1]) {  // 如果 dp[i-1][j] > dp[i][j-1]
        LCS(i-1, j, res);
    } else {  // 否则将 j 减 1
        LCS(i, j-1, res);
    }
}

int main() {
    int m, n;
    cin >> m >> n;
    X.resize(m);
    Y.resize(n);
    for (int i = 0; i < m; i++) cin >> X[i];
    for (int i = 0; i < n; i++) cin >> Y[i];

    // 初始化 dp 数组
    dp.resize(m+1, vector<int>(n+1, 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]);
            }
        }
    }

    // 找出最长公共子序列
    vector<int> res;
    LCS(m, n, res);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}