解题思路

本题要求找到两个字符串的最短公共超串（Shortest Common Supersequence, SCS），即一个最短的字符串，使得给定的两个字符串都是它的子序列。例如：

• apple + peach → appleach（最短超串）
• ananas + banana → bananas（最短超串）

关键观察

1. 最短公共超串（SCS）与最长公共子序列（LCS）的关系

   • 最短公共超串的长度 = len(s1) + len(s2) - len(LCS(s1, s2))
   • 因此，如果能找到 s1 和 s2 的 LCS，就可以构造 SCS。

2. 动态规划（DP）求解 LCS

   • 定义 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。
   • 状态转移方程：
     • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
     • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 构造最短公共超串

   • 从 dp[m][n] 开始回溯，如果当前字符相等，则加入结果；否则，选择 dp 值较大的方向移动，并加入对应字符。

C++ 代码实现

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

string shortestCommonSupersequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));

    // 计算 LCS 的 DP 表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 回溯构造最短公共超串
    string res;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            res.push_back(s1[i - 1]);
            i--, j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            res.push_back(s1[i - 1]);
            i--;
        } else {
            res.push_back(s2[j - 1]);
            j--;
        }
    }

    // 处理剩余字符
    while (i > 0) {
        res.push_back(s1[i - 1]);
        i--;
    }
    while (j > 0) {
        res.push_back(s2[j - 1]);
        j--;
    }

    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string s1, s2;
    while (cin >> s1 >> s2) {
        cout << shortestCommonSupersequence(s1, s2) << endl;
    }
    return 0;
}