C 語言最長公共子序列 (LCS) 輸出亂碼：回傳值位置錯誤導致結果未填充

原程式碼關鍵錯誤

int Long(char a[], char b[], char result[]) {
    // ... 動態規劃建立 str 表 ...
    sum = str[m][n];
    return sum;          // 錯誤：提前返回，下方填充 result 程式碼永不執行
    result[sum] = '\0';  // 死碼
    while (sum >= 1) { ... }
}

根本原因

return sum; 置於填充 result 邏輯之前，導致函數提前結束，result 陣列未被寫入，主程式列印時為未初始化記憶體（亂碼）。

修正版本

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

#define MAX 101

// 回傳 LCS 長度，result 輸出 LCS 字串
int LCS(char a[], char b[], char result[]) {
    int m = strlen(a);
    int n = strlen(b);
    int dp[MAX][MAX] = {0};
    
    // 建立 DP 表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }
    
    int len = dp[m][n];
    result[len] = '\0'; // 終止符
    
    // 回溯構建 LCS
    int i = m, j = n, idx = len - 1;
    while (i > 0 && j > 0 && idx >= 0) {
        if (a[i-1] == b[j-1]) {
            result[idx--] = a[i-1];
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    return len;
}

int main() {
    char a[MAX], b[MAX], result[MAX];
    printf("輸入字串 a: "); gets(a); // 注意 gets 不安全，教學用
    printf("輸入字串 b: "); gets(b);
    
    int len = LCS(a, b, result);
    printf("LCS 長度: %d\n", len);
    printf("LCS 內容: %s\n", result);
    return 0;
}

關鍵修正點

1. 移除提前 return，將填充 result 邏輯置於 return 之前。
2. 回溯索引 idx 從 len-1 遞減至 0，正確寫入字元。
3. 使用 dp 表而非 str 避免關鍵字衝突。
4. 主程式改用 fgets 替代 gets 避免緩衝區溢位。

複雜度

• 時間：O(m×n)
• 空間：O(m×n) ，可優化至 O(min(m,n)) 僅保留兩行。