POJ 2264 Advanced Fruits - LCS 構造最短公共超序列

題目轉化

給兩字串 s1, s2 (|s| ≤ 100)，求最短字串 s 使 s1、s2 均為其子序列。即最短公共超序列 (SCS)。

關鍵性質：|SCS| = |s1| + |s2| - |LCS|。構造時，將 LCS 字元只保留一次，其餘字元按原序合併。

算法步驟

1. DP 求 lcs[i][j]：s1[0..i-1] 與 s2[0..j-1] 的 LCS 長度。
2. 從 lcs[len1][len2] 逆向回溯，記錄所有 LCS 字元在 s1、s2 中的索引 index1[], index2[]（由後向前）。
3. 在 index 間隙填入非 LCS 字元，最後補上尾部剩餘字元。

關鍵回溯邏輯

int i = len1, j = len2, top = 0;
while (i > 0 && j > 0) {
    if (s1[i-1] == s2[j-1]) {           // 屬於 LCS
        index1[top] = i-1; index2[top] = j-1;
        ++top; --i; --j;
    } else if (lcs[i-1][j] >= lcs[i][j-1]) --i;
    else --j;
}
index1[top] = index2[top] = -1; // 哨兵，便於處理第一段

合併構造

int s_top = 0;
for (int k = top; k >= 1; --k) {
    // 兩 LCS 字元之間的 s1 獨有字元
    for (int p = index1[k] + 1; p < index1[k-1]; ++p) s[s_top++] = s1[p];
    // 兩 LCS 字元之間的 s2 獨有字元
    for (int p = index2[k] + 1; p < index2[k-1]; ++p) s[s_top++] = s2[p];
    // LCS 字元本身（只放一次）
    s[s_top++] = s1[index1[k-1]];
}
// 處理最後一個 LCS 之後的尾部
for (int p = index1[0] + 1; p < len1; ++p) s[s_top++] = s1[p];
for (int p = index2[0] + 1; p < len2; ++p) s[s_top++] = s2[p];
s[s_top] = '\0';

完整代碼

#include 
using namespace std;
const int N = 105;
char s1[N], s2[N], ans[N*2];
int lcs[N][N], idx1[N], idx2[N];

void build_scs() {
    int n = strlen(s1), m = strlen(s2);
    memset(lcs, 0, sizeof(lcs));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (s1[i-1] == s2[j-1]) lcs[i][j] = lcs[i-1][j-1] + 1;
            else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);

    int i = n, j = m, top = 0;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) { idx1[top] = i-1; idx2[top] = j-1; ++top; --i; --j; }
        else if (lcs[i-1][j] >= lcs[i][j-1]) --i;
        else --j;
    }
    idx1[top] = idx2[top] = -1;

    int pos = 0;
    for (int k = top; k >= 1; --k) {
        for (int p = idx1[k] + 1; p < idx1[k-1]; ++p) ans[pos++] = s1[p];
        for (int p = idx2[k] + 1; p < idx2[k-1]; ++p) ans[pos++] = s2[p];
        ans[pos++] = s1[idx1[k-1]];
    }
    for (int p = idx1[0] + 1; p < n; ++p) ans[pos++] = s1[p];
    for (int p = idx2[0] + 1; p < m; ++p) ans[pos++] = s2[p];
    ans[pos] = '\0';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> s1 >> s2) {
        build_scs();
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(|s1|·|s2|) ≤ 10⁴，極快。
• 空間：O(|s1|·|s2|)。

掌握「LCS 回溯 + 間隙合併」模板，SCS 類題目一網打盡。