最長公共子序列（LCS）完整解析與 C 語言實作

最長公共子序列（LCS）完整解析與 C 語言實作

最長公共子序列（Longest Common Subsequence, LCS）是經典動態規劃問題。給定兩個序列 X 與 Y，找出兩者皆為子序列且長度最長的序列 Z。本文詳細說明問題定義、狀態轉移方程、動態規劃表建構，並提供完整 C 語言實作碼，包含長度計算與路徑回溯列印。

問題定義

• 子序列：從原序列刪除零或多個元素後保持順序所得序列。
• 公共子序列：同時為 X 與 Y 子序列的序列。
• 目標：求最大長度 k，並可選擇性列印該子序列。

動態規劃分析

設 d[i][j] 為序列 X[1..i] 與 Y[1..j] 的 LCS 長度。狀態轉移：

d[i][j] = 0                                  (i=0 或 j=0)
d[i][j] = d[i-1][j-1] + 1                    (x_i == y_j)
d[i][j] = max(d[i-1][j], d[i][j-1])          (x_i != y_j)

若需列印 LCS，需另設陣列 p[i][j] 記錄決策來源（1: 左上, 2: 上, 3: 左），遞迴回溯即可重建序列。

完整 C 語言實作

#include <stdio.h>
#include <string.h>
#define MAX 201

int d[MAX][MAX];          // DP 表：LCS 長度
int p[MAX][MAX];          // 決策表：用於回溯
char x[MAX], y[MAX];      // 輸入字串（含結尾 '\0'）

// 僅計算長度
void lcs(const char *x, int m, const char *y, int n) {
    int i, j;
    for (i = 0; i <= m; i++) d[i][0] = 0;
    for (j = 0; j <= n; j++) d[0][j] = 0;
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (x[i-1] == y[j-1])
                d[i][j] = d[i-1][j-1] + 1;
            else
                d[i][j] = (d[i-1][j] > d[i][j-1]) ? d[i-1][j] : d[i][j-1];
        }
    }
}

// 計算長度並記錄決策
void lcs_extend(const char *x, int m, const char *y, int n) {
    int i, j;
    memset(p, 0, sizeof(p));
    for (i = 0; i <= m; i++) d[i][0] = 0;
    for (j = 0; j <= n; j++) d[0][j] = 0;
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (x[i-1] == y[j-1]) {
                d[i][j] = d[i-1][j-1] + 1;
                p[i][j] = 1; // 來自左上
            } else if (d[i-1][j] >= d[i][j-1]) {
                d[i][j] = d[i-1][j];
                p[i][j] = 2; // 來自上方
            } else {
                d[i][j] = d[i][j-1];
                p[i][j] = 3; // 來自左方
            }
        }
    }
}

// 遞迴列印 LCS
void lcs_print(const char *x, int m, int n) {
    if (m == 0 || n == 0) return;
    if (p[m][n] == 1) {
        lcs_print(x, m-1, n-1);
        printf("%c", x[m-1]);
    } else if (p[m][n] == 2) {
        lcs_print(x, m-1, n);
    } else {
        lcs_print(x, m, n-1);
    }
}

int main() {
    while (scanf("%s %s", x, y) != EOF) {
        int lx = strlen(x), ly = strlen(y);
        lcs_extend(x, lx, y, ly);
        printf("%d\n", d[lx][ly]);      // 輸出長度
        // lcs_print(x, lx, ly); puts(""); // 若需列印序列，取消註解
    }
    return 0;
}

範例測試

輸入：
abcfbc abfcab
programming contest
abcd mnp

輸出：
4
2
0

複雜度分析

• 時間複雜度：O(m × n)
• 空間複雜度：O(m × n)（可優化至 O(min(m,n))）

掌握 LCS 不僅能解決字串比對問題，更是動態規劃思維訓練的經典範例，廣泛應用於版本控制、生物資訊、文件差異比較等領域。