C 語言經典算法：最長公共子串（Longest Common Substring）完整實現

問題定義

給定兩個字串，找出它們最長的公共「子串」（連續字符序列），若有多個同長度子串，返回第一個找到的。

算法思路：暴力枚舉優化

• 雙重循環遍歷兩字串所有起始位置組合 (i, j)。
• 若 str1[i] == str2[j]，向後延伸比較，記錄匹配長度。
• 維護全局最大長度及對應子串。
• 時間複雜度 O(n*m*min(n,m))，對短字串（<1000）完全可接受。

完整 C 代碼

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

void getMaxCommonSubstring(char* str1, char* str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int maxLen = 0;
    char maxStr[1000] = {0};

    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            if (str1[i] == str2[j]) {
                int curLen = 1;
                char buff[1000] = {0};
                buff[0] = str2[j];
                // 向後延伸匹配
                for (int k = 1; i + k < len1 && j + k < len2; k++) {
                    if (str1[i + k] != str2[j + k]) break;
                    buff[curLen++] = str2[j + k];
                }
                // 更新最大值
                if (curLen > maxLen) {
                    maxLen = curLen;
                    strcpy(maxStr, buff);
                }
            }
        }
    }
    printf("MaxCommonSubstring:\n%s\nlength:%d\n", maxStr, maxLen);
}

int main() {
    char str1[1000], str2[1000];
    scanf("%s", str1);
    scanf("%s", str2);
    getMaxCommonSubstring(str1, str2);
    return 0;
}

測試範例

輸入:
abcdefg
xyzcde123
輸出:
MaxCommonSubstring:
cde
length:3

進階優化方向

• 動態規劃 (DP)：建立二維表 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 結尾的最長公共後綴長度，時間 O(n*m)，空間 O(n*m) 可優化至 O(min(n,m))。
• 後綴自動機/後綴陣列：線性時間構建，適合超長字串（萬級以上）。

常見錯誤提醒

• 混淆「子串」(Substring, 連續) 與「子序列」(Subsequence, 不必連續)。
• 未處理空字串輸入導致越界。
• 只記錄長度未記錄具體字串內容。