KMP 字串匹配演算法完整解析與 Java 實作

KMP 演算法核心原理

KMP（Knuth-Morris-Pratt）演算法是字串模式匹配領域最經典的演算法之一。它的核心思想在於利用已匹配的資訊，避免主字串指標回溯，從而將匹配時間複雜度降至 O(n+m)。

基本匹配流程

給定主字串 S 與模式串 P，分別用指標 i、j 從頭開始比對：

• 字符相等時，i++、j++ 繼續比對下一位
• 字符不等時，模式串指標 j 回退到 next[j] 位置，主字串指標 i 不動，繼續比對

這相當於將模式串向右平移 j - next[j] 位，充分利用已匹配的前綴資訊。

Next 陣列構建

Next 陣列記錄模式串每個位置的最長公共前後綴長度，是 KMP 的關鍵：

public static int[] buildNext(char[] pattern) {
    int len = pattern.length;
    int[] next = new int[len];
    next[0] = 0;
    if (len > 1) next[1] = 0;
    
    for (int i = 2; i < len; i++) {
        int k = next[i - 1];
        while (k >= 0) {
            if (pattern[i - 1] == pattern[k]) {
                next[i] = k + 1;
                break;
            }
            k = (k == 0) ? -1 : next[k];
        }
    }
    return next;
}

KMP 匹配主流程

public int kmpSearch(char[] text, char[] pattern) {
    int[] next = buildNext(pattern);
    int i = 0, j = 0;
    int n = text.length, m = pattern.length;
    
    while (i < n && j < m) {
        if (text[i] == pattern[j]) {
            i++; j++;
        } else {
            j = next[j];
            if (j == 0) i++; // 關鍵：j 歸零時主串指標才前進
        }
    }
    return (j == m) ? i - j : -1;
}

進階：NextVal 優化陣列

當模式串存在重複字符時，標準 next 陣列可能導致多餘比對。NextVal 在 next 基礎上進一步優化：若 pattern[j] == pattern[next[j]]，則 nextval[j] = nextval[next[j]]，直接跳過相同字符。

public int[] buildNextVal(char[] pattern) {
    int len = pattern.length;
    int[] nextVal = new int[len];
    nextVal[0] = -1;
    int i = -1, j = 0;
    while (j < len - 1) {
        if (i == -1 || pattern[j] == pattern[i]) {
            ++i; ++j;
            nextVal[j] = (pattern[j] != pattern[i]) ? i : nextVal[i];
        } else {
            i = nextVal[i];
        }
    }
    return nextVal;
}

複雜度分析與應用場景

• 時間複雜度：O(n+m)，主串指標不回溯
• 空間複雜度：O(m)，儲存 next/nextval 陣列
• 適用場景：大文本搜尋、DNA 序列比對、編譯器詞法分析、防火牆入侵檢測等

掌握 KMP 的關鍵在於理解「失配時模式串應平移多少位」這一核心邏輯，next 陣列正是這一邏輯的預計算結果。