在 text 裡找 pattern，暴力法 O(nm) 太慢？KMP 說：「你已經比對過的資訊別浪費，我幫你跳。」這一跳就從 O(nm) 變成了 O(n+m)。
先講結論
單次字串匹配用 KMP。多模式匹配用 Rabin-Karp。找回文用 Manacher。面試只考前兩個居多，Manacher 屬於加分項。
| 演算法 | 時間 | 特點 |
|---|---|---|
| 暴力 | O(nm) | 簡單但慢 |
| KMP | O(n+m) | 不回退 text 指標 |
| Rabin-Karp | O(n+m) 平均 | 滾動雜湊 |
| Z Algorithm | O(n+m) | Z 陣列 |
| Manacher | O(n) | 回文專用 |
暴力法：為什麼慢
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && text[i+j] == pattern[j]) j++;
if (j == m) found(i);
}每次不匹配就從頭開始比。如果 text 是 “AAAAAAB”、pattern 是 “AAAB”，每次比到最後一個字元才發現不對，再回到起點下一格重來。浪費。
KMP：不走回頭路
KMP 的核心洞見是：不匹配時，text 的指標不回退。它靠一個 LPS（Longest Proper Prefix which is also Suffix）陣列，決定 pattern 的指標要跳到哪。
pattern: A B A B C A B A B
LPS: 0 0 1 2 0 1 2 3 4
LPS[3] = 2 → "ABAB" 最長的「前綴同時也是後綴」是 "AB"，長度 2
匹配過程中不匹配時，j 跳到 lps[j-1]，而不是歸零。因為 LPS 告訴我們「前面已經有一段跟 pattern 開頭一樣了，不用重比」。
int[] computeLPS(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}LPS 陣列的建立本身也是 O(m)。說實話我第一次看 KMP 的時候完全看不懂，看了三遍才搞清楚那個 len = lps[len-1] 在幹嘛。
Rabin-Karp：用 hash 偷懶
與其逐字比對，不如算 hash。視窗滑動時，O(1) 算出新 hash。
text: ABCDE
hash("ABC") = 65×256² + 66×256 + 67
滑動：
hash("BCD") = (hash("ABC") - 65×256²) × 256 + 68
hash 相同才逐字比對（避免碰撞）。平均 O(n+m)，最差 O(nm)。
Rabin-Karp 的殺手鐧是多模式匹配：同時找多個 pattern，hash 比對比 KMP 一個一個找快得多。抄襲檢測系統就是靠這個。
Z Algorithm
z[i] = 從位置 i 開始跟字串開頭能匹配多長。
s: a a b x a a b
z: 7 1 0 0 3 1 0
用途：把 pattern + "$" + text 串起來算 Z 陣列，找 z[i] == m 的位置就是匹配位置。
Manacher：O(n) 找最長回文
暴力找回文是 O(n²)，Manacher 利用回文的對稱性降到 O(n)。技巧是在每個字元間插入特殊字元（如 #），把奇偶長度統一處理。
這個演算法的思路不複雜，但實作細節很煩。面試中被考到的機率不高，但如果你能寫出來，絕對是加分。
選哪個？
- 一般字串搜尋：KMP。穩定 O(n+m)，沒有最差情況
- 同時搜多個 pattern：Rabin-Karp
- 需要前綴資訊：Z Algorithm
- 回文相關：Manacher
日常開發中你大概不會自己寫這些（語言內建的 indexOf / includes 已經夠用），但面試要手寫的時候，KMP 是你的首選。
KMP 的三位發明人（Knuth、Morris、Pratt）可能沒想到，他們 1977 年的論文會成為 2025 年每個軟體工程師面試的噩夢。