最長公共子序列（LCS）算法全解析：遞歸、DP矩陣、連續子串優化

問題定義

給定兩字符串，求最長公共子序列（LCS）長度。子序列可不連續；若要求連續則為最長公共子串。

一、遞歸實現（不連續子序列）

int lcs_len(char *a, int bega, int enda, char *b, int begb, int endb) {
    if (bega > enda || begb > endb) return 0;
    if (a[bega] == b[begb])
        return lcs_len(a, bega+1, enda, b, begb+1, endb) + 1;
    else
        return max(lcs_len(a, bega, enda, b, begb+1, endb),
                   lcs_len(a, bega+1, enda, b, begb, endb));
}

時間復雜度指數級，僅供教學。

二、動態規劃矩陣法（不連續子序列，O(mn)）

int my_lcs(char a[], char b[]) {
    int m = strlen(a), n = strlen(b);
    for (int i=0; i

三、連續子串優化（最長公共子串，O(mn)）
矩陣定義變更：c[i][j] 表示以 a[i] 和 b[j] 結尾的公共子串長度。
if (a[i] == b[j]) c[i][j] = c[i-1][j-1] + 1;
else c[i][j] = 0;  // 不連續則歸零

// 遍歷過程中記錄最大值及位置，直接得到長度與終點

避免了事後掃描矩陣尋找最長對角線，效率更高。

本文出自「菜鳥的進階之路」博客，轉載請保留出處：原文鏈接