KMP 字串比對

🎯 什麼情境該想到我

當你「要在一個長文字裡找一個樣式」的時候。
★ 但實務上你幾乎永遠該用標準庫的 strings.Index——這頁的價值在於理解**「失配時已知的資訊不該被丟掉」**這個思想，以及它衍生出的前綴函式在其他題目上的用途。

⚙️ 怎麼用（機制與推導）

樸素比對的浪費

文字： A B A B A B C
樣式： A B A B C
       ✓ ✓ ✓ ✓ ✗       在位置 4 失配

樸素做法：文字指標退回位置 1，樣式從頭開始 → ★ 白白丟掉「前 4 個字元是 ABAB」這個資訊

★ KMP 的核心洞察：失配時，我們已經知道文字中剛才那一段長什麼樣（就是樣式的前綴）。
利用這個資訊，文字指標永遠不用回退。

★ 前綴函式（失配函式）

$\pi [i]=\text{pattern}[\mathrm{0..}i]\text{ 中，「既是真前綴、又是後綴」的最長長度}$

pattern:  A  B  A  B  C
索引:     0  1  2  3  4
π:        0  0  1  2  0
                ↑  ↑
                │  └─ "ABAB" 的最長「真前綴=後綴」是 "AB"，長度 2
                └──── "ABA"  的是 "A"，長度 1

失配時怎麼用：在位置 $j$ 失配 → 樣式指標跳到 $\pi [j-1]$，文字指標不動。
意思是：「前面匹配的那一段的後綴，正好也是樣式的前綴，所以那一段不用重比。」

實作

// 建前綴函式
func buildPi(p string) []int {
    pi := make([]int, len(p))
    k := 0
    for i := 1; i < len(p); i++ {
        for k > 0 && p[i] != p[k] {
            k = pi[k-1]           // ★ 失配就往回跳（和主迴圈用同一個邏輯）
        }
        if p[i] == p[k] { k++ }
        pi[i] = k
    }
    return pi
}
 
// 比對
func KMP(text, pattern string) []int {
    if len(pattern) == 0 { return nil }
    pi := buildPi(pattern)
    var res []int
    k := 0
    for i := 0; i < len(text); i++ {        // ★ i 永遠只往前，不回退
        for k > 0 && text[i] != pattern[k] {
            k = pi[k-1]
        }
        if text[i] == pattern[k] { k++ }
        if k == len(pattern) {
            res = append(res, i-k+1)
            k = pi[k-1]                     // ★ 繼續找下一個（允許重疊）
        }
    }
    return res
}

★ buildPi 和主迴圈的結構一模一樣——建前綴函式其實就是「樣式和自己比對」。
看出這一點，兩段程式碼就只要記一段。

★ 為什麼是 $O(n+m)$（攤還分析）

主迴圈裡的內層 for k > 0 && ... 看起來像是巢狀迴圈，但：

• k 每次外層迭代最多 +1 → 整個過程 k 總共增加最多 $n$ 次
• 內層每執行一次，k 至少 -1（因為 $\pi [k-1]<k$）
• k 不會變成負數

→ 內層的總執行次數 $\le$ k 的總增加量 $=n$。

$\text{總成本}=O(n)+O(n)=O(n)$

★ 這是攤還分析的經典範例（和 堆疊與佇列 的 append 同一套思路）：
單次操作可能很貴，但「貴的次數」被另一個量綁住了。

預處理	$O(m)$
比對	$O(n)$
空間	$O(m)$

和其他字串比對演算法

演算法	複雜度	特點
樸素	$O(nm)$ 最差	★ 但實務上平均很快，短樣式時常勝過 KMP
KMP	$O(n+m)$	最差有保證；文字指標不回退 → 適合串流
Boyer-Moore	最好 $O(n/m)$	★ 從後往前比，可以「跳過」大段文字。實務上最快，多數標準庫用它的變體
Rabin-Karp	平均 $O(n+m)$	滾動雜湊；★ 多樣式比對很好用
Aho-Corasick	$O(n+\sum m_i+z)$	★ 同時找很多個樣式（敏感詞過濾、入侵偵測）

★ Go 的 strings.Index 用的是混合策略（短樣式用暴力+特殊指令、長樣式用 Rabin-Karp 類），
實測幾乎總是比手寫 KMP 快。不要自己寫。

★ 前綴函式的其他用途（比 KMP 本身更常用）

用途	做法
最小週期	字串 $s$ 的最小週期 = $n-\pi [n-1]$（若能整除）。判斷「這個字串是不是由某段重複而成」
最長回文前綴	對 $s+\text{\#}+\text{reverse}(s)$ 建前綴函式
兩字串的最長公共前後綴	對 $a+\text{\#}+b$ 建
KMP 自動機	把 $\pi$ 展開成狀態機，每步 $O(1)$ 無回退——適合硬體或串流

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 實務上用標準庫。Go 的 strings.Index / strings.Contains / bytes.Index，或 regexp（複雜樣式）。
• ★ 短樣式上 KMP 反而比暴力慢。$\pi$ 的建立與間接跳轉有常數開銷，而現代 CPU 對暴力比對的分支預測與 SIMD 很友善。
• Unicode 要小心：Go 的 string 是 UTF-8 位元組序列，按 byte 比對可能切在字元中間。
  處理中文要 []rune（但會多一次配置），或確認樣式本身是完整的 UTF-8 序列（此時按 byte 比對是安全的）。
• 多個樣式要找 → 用 Aho-Corasick，不要對每個樣式各跑一次 KMP。
• 模糊比對／編輯距離 是完全不同的問題 → 見 動態規劃，或資料庫端的 工具-用trigram索引加速模糊查詢。
• buildPi 的邊界容易寫錯：k = pi[k-1] 中的 k-1、以及找到匹配後的 k = pi[k-1]——兩處都不是 k = 0。

🔗 相關工具

• 動態規劃 —— 模糊比對（編輯距離）用 DP，不是 KMP
• 堆疊與佇列 —— 攤還分析的同一套推導
• 雜湊表 —— Rabin-Karp 的滾動雜湊
• 工具-用trigram索引加速模糊查詢 —— 資料庫端的字串比對加速
• 演算法導論