KMP 算法深度解析：Next 陣列構建與模式匹配全流程圖解

編輯：關於C語言

KMP 算法核心原理：從暴力匹配到高效跳躍

在字串匹配問題中，KMP (Knuth-Morris-Pratt) 算法以其 O(n+m) 的線性時間複雜度，成為經典教科書級別的解決方案。不同於暴力匹配在失配時將模式串回溯到開頭，KMP 算法的核心在於預處理模式串生成 Next 陣列，利用已匹配部分的前綴後綴資訊，直接決定下一輪匹配的起始位置，避免了主串指針的回溯，從而實現了效率的質變。

Next 陣列：KMP 的「導航儀」

Next 陣列（部分匹配表）記錄了模式串中每個位置之前的子串，其最長公共前綴後綴長度。當模式串 T 與主串 S 在位置 j 處失配時，Next[j] 指示 T 應從哪個位置繼續與 S 當前字元匹配。關鍵在於 Next 陣列僅與模式串 T 相關，與主串 S 無關，因此可預先計算。

Next 陣列構建過程逐步演示

以模式串 T = "ababaaaba" (索引 1~9) 為例，Next 陣列計算過程如下表所示：

Index	1	2	3	4	5	6	7	8	9
T[i]	a	b	a	b	a	a	a	b	a
Next[i]	0	1	1	2	3	4	2	2	3

構建邏輯採用雙指針 i（當前計算位置）和 j（前綴長度/下一匹配位置）：

初始化：next[1] = 0, i=2, j=1
匹配成功 (T[i] == T[j])：i++, j++, next[i] = j
失配且 j > 0：j = next[j]（遞歸式回退，尋找更短的公共前綴後綴）
失配且 j == 0：i++, j=1, next[i] = 0

關鍵步驟圖解 (Step 6~7)

當 i=7 (T[7]='a'), j=5 (T[5]='a') 匹配成功後，i=8, j=6, next[8]=6。隨後 T[8]='b' 與 T[6]='a' 失配，j 回退至 next[6]=4，再比較 T[8] 與 T[4] 仍失配，j 回退至 next[4]=2，此時 T[8]='b' 與 T[2]='b' 匹配，流程繼續。這完美展示了 Next 陣列如何指導「跳躍」。

前綴與後綴：Next 陣列的數學基石

理解 Next 陣列需掌握兩個概念：

前綴：包含首字元、不含尾字元的所有連續子串。如 "ababa" 的前綴集：{a, ab, aba, abab}
後綴：包含尾字元、不含首字元的所有連續子串。如 "ababa" 的後綴集：{a, ba, aba, baba}

Next[i] 的值，即為子串 T[1...i-1] 的最長公共前綴後綴長度。這意味著當第 i 位失配時，前 i-1 位已匹配成功，其最長公共前綴後綴部分在主串中已被驗證，下一輪只需從後綴的下一位（即前綴長度+1）開始匹配。

C 語言完整實現

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

void getNext(char* T, int* next) {
    int i = 1, j = 0;
    next[1] = 0;
    int len = strlen(T + 1); // 假設 T 從索引 1 開始
    while (i < len) {
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int KMP(char* S, char* T, int startPos) {
    int i = startPos, j = 1;
    int next[100];
    getNext(T, next);
    int sLen = strlen(S + startPos);
    int tLen = strlen(T + 1);

    while (i <= sLen && j <= tLen) {
        if (j == 0 || S[i] == T[j]) {
            i++; j++;
        } else {
            j = next[j];
        }
    }
    return (j > tLen) ? (i - tLen) : 0;
}

int main() {
    char S[20] = " absfeafdababaaaba"; // 索引 1 開始
    char T[20] = " ababaaaba";
    printf("匹配位置: %d\n", KMP(S, T, 1)); // 輸出 8
    return 0;
}

複雜度分析與優化方向

時間複雜度：預處理 O(m)，匹配 O(n)，總計 O(n+m)
空間複雜度：O(m) 存儲 Next 陣列
優化點：標準 Next 陣列在連續相同字元時（如 "aaaaab"）跳躍效率不高，可構建 Nextval 陣列：若 T[i] == T[next[i]]，則 nextval[i] = nextval[next[i]]，直接跳過值相同的位置，進一步減少比較次數。