最長公共子字符串：動態規劃解法詳解與C語言實現

編輯：關於C語言

問題理解：子字符串與子序列的區別

在探討最長公共子字符串問題時，首先必須釐清它與「最長公共子序列（LCS）」的根本不同。子字符串要求在原字符串中連續出現，而子序列則不要求連續。這一特性決定了我們可以採用動態規劃來高效求解，但如何構建狀態轉移表是關鍵所在。

解空間分析

給定兩字符串 str1（長度 len1）與 str2（長度 len2），若公共子字符串以 str1 第 i 位和 str2 第 j 位結束，則解空間大小上限為 len1 × len2。暴力遍歷所有可能的結束位置組合，再向前匹配長度，時間複雜度高達 O(n³)，顯然不可取。

動態規劃的最優子結構

動態規劃的核心在於尋找「最優子結構」——即大問題的最優解包含子問題的最優解。對於本題，我們定義二維表 count[i][j] 表示：以 str1[i] 和 str2[j] 為結尾的最長公共子字符串長度。

狀態轉移邏輯極其簡潔：

情況 1： str1[i] == str2[j] → 當前長度 = 左上角長度 + 1，即 count[i][j] = count[i-1][j-1] + 1
情況 2： str1[i] != str2[j] → 無法形成公共子字符串，count[i][j] = 0

表的構建順序為自上而下、自左而右（即從字符串頭部向尾部推進）。構建過程中同步記錄最大長度及其結束位置，即可在 O(len1 × len2) 時間內解決問題。

表構建示例

以 str1 = "1234"、str2 = "2345" 為例，動態規劃表的填充過程如下圖所示：

C語言完整實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void lcs_substring(char *str1, char *str2, int len1, int len2) {
    // 動態分配一維數組模擬二維表
    int *record = (int *)malloc(len1 * len2 * sizeof(int));
    int maxLen = 0, maxH = 0, maxW = 0;

    for (int h = 0; h < len1; h++) {
        for (int w = 0; w < len2; w++) {
            if (str1[h] == str2[w]) {
                if (h == 0 || w == 0)
                    record[h * len2 + w] = 1;
                else
                    record[h * len2 + w] = record[(h-1) * len2 + w - 1] + 1;

                if (maxLen < record[h * len2 + w]) {
                    maxLen = record[h * len2 + w];
                    maxH = h;
                    maxW = w;
                }
            } else {
                record[h * len2 + w] = 0;
            }
        }
    }

    // 輸出最長公共子字符串
    if (maxLen > 0) {
        for (int i = maxW - maxLen + 1; i <= maxW; i++)
            printf("%c", str2[i]);
    }
    printf("\n長度: %d\n", maxLen);
    free(record);
}

int main() {
    char *str1, *str2;
    int len1, len2;
    printf("輸入兩字符串長度: ");
    scanf("%d %d", &len1, &len2);
    str1 = (char *)malloc(len1 + 1);
    str2 = (char *)malloc(len2 + 1);
    printf("輸入兩字符串: ");
    scanf("%s %s", str1, str2);
    lcs_substring(str1, str2, len1, len2);
    free(str1);
    free(str2);
    return 0;
}