KMP 字符串匹配算法深度解析：從有限自動機到 Next 數組優化

算法背景

KMP (Knuth-Morris-Pratt) 算法以 O(m+n) 時間復雜度解決模式串在文本串中的匹配問題，核心在於利用「部分匹配」信息避免主串指針回溯，將模式串向右滑動最大可能距離。

有限自動機視角理解

KMP 實質是構建一個確定性有限自動機 (DFA)：

• 狀態：已匹配的模式串前綴長度 (0 ~ m)。
• 轉移：匹配成功 → 狀態+1；失敗 → 根據「最長公共前後綴」跳轉到較小狀態繼續匹配。
• Next 數組：即失效函數/狀態轉移表，next[j] 表示模式串第 j 位失配時應跳轉的狀態 (即最長公共前後綴長度)。

Next 數組構造 (標準版)

next[0] = -1 (或 0，視實現)。對於 i > 0，已知 next[i-1] = k：

1. 若 P[i] == P[k]，則 next[i] = k+1。
2. 若 P[i] != P[k] 且 k > 0，令 k = next[k-1]，重複判斷。
3. 若 k == 0 仍不等，next[i] = 0。

// 標準版 (0-based 索引)
void get_next(const char *P, int m, int *next) {
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < m; i++) {
        while (k >= 0 && P[i] != P[k+1]) k = next[k];
        if (P[i] == P[k+1]) k++;
        next[i] = k;
    }
}

Next 數組優化 (修正版)

標準版存在「多比較」問題：若 P[i] == P[next[i]]，失配時會跳轉到相同字符再次比較。優化：若 P[i] == P[k] 則 next[i] = next[k]，直接跳過相同字符。

void get_next_optimized(const char *P, int m, int *next) {
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < m; i++) {
        while (k >= 0 && P[i] != P[k+1]) k = next[k];
        if (P[i] == P[k+1]) k++;
        // 優化點
        if (i+1 < m && P[i+1] == P[k+1]) next[i] = next[k];
        else next[i] = k;
    }
}

匹配過程

int kmp_search(const char *S, int n, const char *P, int m, const int *next) {
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == P[j]) { i++; j++; }
        else j = next[j] + 1; // next 存的是索引，+1 對應狀態
    }
    return (j == m) ? (i - m) : -1;
}

複雜度證明要點

• Next 構造：k 只增不減，總回溯次數 ≤ m，故 O(m)。
• 匹配：i 只增不減，j 總增加 ≤ n，總回溯 ≤ n，故 O(n)。
• 總計 O(m+n)，空間 O(m)。

工程應用提示

• 多模式匹配請用 AC 自動機 (Aho-Corasick)。
• 需求最長公共前綴/後綴、周期性判斷、字符串最小循環節等，均可利用 Next 數組衍生。
• C++ std::search (Boyer-Moore-Horspool) 在隨機文本上常比 KMP 快，但最壞 O(mn)；KMP 保證最壞線性，適合實時系統。

總結

KMP 通過「模式串自我分析」預計算 Next 數組，將匹配過程轉化為 DFA 確定性轉移，實現了理論最優的線性時間匹配。理解其「最長公共前後綴」核心邏輯，是掌握進階字符串算法 (AC 自動機、後綴自動機、Z-algorithm) 的基石。