KMP 字串匹配算法：原理圖解、Next 陣列構建與 Java 完整實現

為什麼需要 KMP？

傳統暴力匹配 (Brute Force) 在失配時將模式串回溯到開頭，主串指針回退，時間複雜度 O(M×N)。KMP 通過**預處理模式串**，構建 next 陣列 (又稱「部分匹配表」/「失敗函數」) 記錄「真前綴 = 真後綴」的最大長度，**避免主串回溯、模式串利用已匹配資訊跳躍**，達到 O(M+N) 線性複雜度。

核心概念：前綴、後綴與 Next 陣列

• 前綴： 除最後一字元外的所有頭部子串
• 後綴： 除第一字元外的所有尾部子串
• next[i] = j： 模式串前 i 字元 (下標 0~j-1) 的最長真前綴等於最長真後綴，長度為 j
• 約定：next[0] = 0 (或 -1，視實作風格)

範例：模式串 "ABCDABD"

Next 陣列構建算法 (O(N))

// 模式串 pat 長度 m，next 陣列長度 m+1 (或 m)
void buildNext(String pat, int[] next) {
    int m = pat.length();
    next[0] = 0; // 或 -1
    int k = 0;   // 當前最長前後綴長度
    
    for (int i = 1; i < m; i++) { // i 從 1 開始 (對應第 2 字元)
        // 失配時回退：利用已計算的 next[k]
        while (k > 0 && pat.charAt(i) != pat.charAt(k)) {
            k = next[k - 1]; // 或 next[k] 視定義
        }
        // 匹配則延伸
        if (pat.charAt(i) == pat.charAt(k)) {
            k++;
        }
        next[i] = k; // 或 next[i+1] = k
    }
}

關鍵洞見： k = next[k-1] 代表「縮短前綴長度，嘗試更短的前後綴匹配」，這是 KMP 避免重複比較的核心。

匹配過程 (O(M))

List<Integer> kmpSearch(String text, String pat) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pat.length();
    int[] next = new int[m];
    buildNext(pat, next);
    
    int j = 0; // 模式串指針
    for (int i = 0; i < n; i++) { // 主串指針 i 不回退
        while (j > 0 && text.charAt(i) != pat.charAt(j)) {
            j = next[j - 1]; // 模式串跳躍
        }
        if (text.charAt(i) == pat.charAt(j)) {
            j++;
        }
        if (j == m) { // 完全匹配
            res.add(i - m + 1); // 記錄起始位置
            j = next[j - 1];    // 繼續尋找下一個匹配
        }
    }
    return res;
}

Java 完整可執行代碼

import java.util.ArrayList;
import java.util.List;

public class KMP {
    public static void main(String[] args) {
        String text = "1kk23789456789hahha";
        String pattern = "789";
        
        List<Integer> matches = kmpSearch(text, pattern);
        if (matches.isEmpty()) {
            System.out.println("匹配不成功");
        } else {
            for (int pos : matches) {
                System.out.println("匹配發生在索引: " + pos);
            }
        }
    }

    static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> res = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) return res;
        
        int[] next = buildNext(pattern);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                res.add(i - m + 1);
                j = next[j - 1];
            }
        }
        return res;
    }

    static int[] buildNext(String pat) {
        int m = pat.length();
        int[] next = new int[m];
        next[0] = 0;
        int k = 0;
        for (int i = 1; i < m; i++) {
            while (k > 0 && pat.charAt(i) != pat.charAt(k)) {
                k = next[k - 1];
            }
            if (pat.charAt(i) == pat.charAt(k)) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }
}

複雜度分析

進階變體與延伸

• Nextval (優化 Next)： 當 pat[i] == pat[next[i]] 時，nextval[i] = nextval[next[i]]，避免冗餘比較。
• BM / Sunday 算法： 從模式串尾部比較，實務中對短模式串常比 KMP 更快 (跳躍更大)。
• 多模式匹配 (AC 自動機)： 在主串中一次查找多個模式串，構建 Trie + 失敗指針。

常見錯誤避坑

1. Next 陣列下標定義不一致： 代碼中統一用「next[i] 表示前 i+1 字元的最長前後綴長度」，或「next[i] 表示前 i 字元」。務必統一。
2. 死循環： while (j > 0 && ...) 條件缺少 j > 0 導致 j=0 時無限回退。
3. 匹配後未重置 j： 找到匹配需 j = next[j-1] 繼續搜尋，否則漏配或越界。

結語

KMP 是字串算法的經典入門，掌握 **Next 陣列「利用已知匹配資訊跳過無效比較」** 的核心思想，不僅能解決精確匹配，更是理解 AC 自動機、字串周期性分析等進階主題的基石。