C 語言 KMP 算法可視化：在匹配過程中輸出每一趟比較詳情

KMP 核心流程回顧

1. 預處理模式串 T，構建 nextval 數組（失敗函數）。
2. 主串 S 與模式串 T 雙指針 i, j 掃描：
     • 匹配成功：i++, j++
     • 匹配失敗：j = nextval[j]（模式串右移）
3. j == T.length 時匹配成功，返回起始下標。

插桩輸出每一趟比較

在 KMPIndex 函數的核心判斷處添加打印：

int KMPIndex(SqString s, SqString t) {
    int nextval[MaxSize], i = 0, j = 0;
    GetNextval(t, nextval);
    int step = 0;
    while (i < s.length && j < t.length) {
        step++;
        // 關鍵：輸出當前比較的字符、下標、nextval 值
        printf("[Step %3d] i=%2d('%c')  j=%2d('%c')  nextval[j]=%2d\n",
               step, i, s.data[i], j, t.data[j], nextval[j]);

        if (j == -1 || s.data[i] == t.data[j]) {
            i++; j++;
        } else {
            j = nextval[j];
        }
    }
    if (j >= t.length) return i - t.length;
    return -1;
}

輸出示例

[Step   1] i= 0('a')  j= 0('a')  nextval[j]=-1
[Step   2] i= 1('b')  j= 1('b')  nextval[j]= 0
[Step   3] i= 2('c')  j= 2('c')  nextval[j]= 0
[Step   4] i= 3('a')  j= 3('a')  nextval[j]= 0
[Step   5] i= 4('a')  j= 4('b')  nextval[j]= 0   // 失敗，j 回溯
[Step   6] i= 4('a')  j= 0('a')  nextval[j]=-1   // 繼續比較
...
匹配,從第 10 個數開始

進階：可視化 nextval 構建過程

同理在 GetNextval 中打印 j, k, t.data[j], t.data[k], nextval[j]，觀察前綴表生成邏輯。

教學意義

• 幫助理解「為什麼不需要回溯主串指針 i」。
• 直觀展示 nextval 如何實現「模式串自我遷移」。
• 調試自寫 KMP 時定位邏輯錯誤（如 nextval 計算越界、字符比較條件寫反）。