String Algorithms · 比較表
字串比對演算法比較
字串雜湊、Rabin-Karp、KMP、Z 演算法、Manacher、字典樹：預處理誰、保證什麼、各自擅長的問題形狀。
| 演算法 | 時間 | 空間 | 預處理 | 保證 | 問題形狀 | 難度 |
|---|---|---|---|---|---|---|
| String Hashing字串雜湊 | O(n) | O(n) | 文字（前綴雜湊） | 機率正確 | 任意子字串 O(1) 比較 | 進階 |
| Rabin-Karp滾動雜湊比對 | 平均 O(n+m) | O(1) | 模式（一個雜湊值） | 平均 O(n+m) | 多個模式同時找 | 進階 |
| KMP前綴函數比對 | O(n+m) | O(m) | 模式（失敗函數） | 最壞 O(n+m) | 單一模式、串流文字 | 困難 |
| Z-AlgorithmZ 函數 | O(n+m) | O(n) | 模式 + 文字（串接） | 最壞 O(n+m) | 每個位置的最長前綴匹配 | 困難 |
| Manacher最長回文 | O(n) | O(n) | 文字（插入分隔符） | O(n) | 回文 | 困難 |
| Trie Applications字典樹應用 | O(L) | O(ΣL) | 字典（所有模式） | O(L) 每次查詢 | 前綴查詢、字典比對 | 進階 |
什麼時候選哪一個
String Hashing 字串雜湊
要比很多對子字串是否相等、找最長重複子字串、配合二分。用雙模數把碰撞機率壓到可忽略。
Rabin-Karp 滾動雜湊比對
同時找很多個等長模式（抄襲比對、病毒特徵）：把所有模式的雜湊放進集合，滾動一遍文字。單一模式沒有比 KMP 好。
KMP 前綴函數比對
單一模式的標準答案，文字可以一個字一個字餵進來（不必整段在記憶體）。失敗函數本身也能算週期、最短回文補齊。
Z-Algorithm Z 函數
問「每個位置往後能和開頭匹配多長」時比 KMP 直觀：字串週期、最短重複單元、前綴出現次數。
Manacher 最長回文
最長回文子字串、以每個中心的回文半徑、回文子字串計數。只管回文，其他什麼都不做。
Trie Applications 字典樹應用
自動補全、以前綴計數、判斷一個字能否由字典拼出。模式集合固定、查詢很多次時最划算。
選擇指南
- 一個模式、一段文字 → KMP。要簡單一點可以用內建
find／strstr，它們通常也是線性的。 - 很多模式 → 等長用 Rabin-Karp 的雜湊集合；不等長且要一次全找出來，是 Aho-Corasick（字典樹 + KMP 的合體，本站未收錄）。
- 子字串相等、重複、比較 → 字串雜湊。它是唯一能 O(1) 比較任意兩段的方法，代價是機率正確。
- 回文 → Manacher。中心擴展 O(n²) 在 n ≤ 1000 也夠用，先寫得對再換。
- 前綴 → 字典樹。後綴或任意子字串的結構問題 → 後綴陣列／後綴自動機（本站未收錄）。