解题思路

这道题要求我们找到两个单词序列的最长公共子序列（LCS），即在不改变单词顺序的情况下，找出两个序列共有的最长单词序列。

关键步骤

1. 输入处理
   • 读取两段文本，每段以 # 结束，存储为 vector<string> 或类似结构。
2. 动态规划求解 LCS
   • 定义 dp[i][j] 表示第一个序列前 i 个单词和第二个序列前 j 个单词的 LCS 长度。
   • 状态转移方程：
     • 如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
     • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 回溯构造 LCS
   • 从 dp[m][n] 开始，逆向查找哪些单词被选中。

C++ 代码实现

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

vector<string> getLCS(const vector<string>& A, const vector<string>& B) {
    int m = A.size(), n = B.size();
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));

    // 动态规划填表
    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]);
            }
        }
    }

    // 回溯构造 LCS
    vector<string> lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            lcs.push_back(A[i - 1]);
            i--, j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(lcs.begin(), lcs.end()); // 因为是逆向回溯，需要反转
    return lcs;
}

int main() {
    while (true) {
        vector<string> A, B;
        string word;

        // 读取第一个文本，直到遇到 #
        while (cin >> word && word != "#") {
            A.push_back(word);
        }

        // 读取第二个文本，直到遇到 #
        while (cin >> word && word != "#") {
            B.push_back(word);
        }

        // 如果输入结束（没有更多测试用例）
        if (A.empty() && B.empty()) break;

        // 计算并输出 LCS
        vector<string> lcs = getLCS(A, B);
        for (int i = 0; i < lcs.size(); i++) {
            if (i > 0) cout << " ";
            cout << lcs[i];
        }
        cout << endl;
    }
    return 0;
}