POJ 2250 Compromise：單詞級最長公共子序列 (LCS) 詳解

void lcs() {
    memset(d, 0, sizeof(d));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i < la; ++i)
        for (int j = 1; j < lb; ++j)
            if (!strcmp(a[i], b[j])) {
                d[i][j] = d[i-1][j-1] + 1;
                pre[i][j] = 1; // 匹配
            } else if (d[i-1][j] > d[i][j-1]) {
                d[i][j] = d[i-1][j];
                pre[i][j] = 2; // 來自上
            } else {
                d[i][j] = d[i][j-1];
                pre[i][j] = 3; // 來自左
            }
}

遞歸輸出路徑

void print(int i, int j) {
    if (pre[i][j] == 1) {
        print(i-1, j-1);
        if (flag) flag = 0; else printf(" ");
        printf("%s", a[i]);
    } else if (pre[i][j] == 2) print(i-1, j);
    else if (pre[i][j] == 3) print(i, j-1);
}

輸入處理關鍵

while (scanf("%s", a[1]) != EOF) {
    la = 1;
    while (scanf("%s", a[++la]), a[la][0] != '#'); // 讀第一段
    lb = 0;
    while (scanf("%s", b[++lb]), b[lb][0] != '#'); // 讀第二段
    lcs();
    print(la-1, lb-1);
    printf("\n");
}

注意事項

• 單詞比較用 strcmp，區分大小寫（題目均為小寫）。
• pre 數組僅需存方向，空間 O(N²) 完全可行（N≤100）。
• 多組測試用例，直到 EOF。

此題是 LCS 經典應用的「單詞版」，掌握 dp + path 模板可解決所有需輸出具體序列的 LCS 變體。