字串不能直接拿來當陣列的 key；但把字串映射成一個整數，就可以。
字串比較為什麼慢？
判斷兩個子字串是否相同，暴力做法是逐字元比對——O(m)，m 是子字串長度。
如果你在解「最長公共子字串」，需要枚舉所有長度和起始位置，每次比對 O(m)，總共 O(n²m)——在 n = 10^4 時就超時了。
Rolling Hash 的思路：把每個子字串映射成一個整數。整數比較是 O(1)，雜湊值相同則子字串大概率相同。
多項式雜湊
把字串看成多項式的係數：
hash("abc") = 'a' × p² + 'b' × p¹ + 'c' × p⁰ (mod m)
p = base，通常選 131（比 26 大的質數）
m = modulus，通常選大質數 10⁹+7 或 10⁹+9前綴雜湊：預先計算每個前綴的雜湊值，然後 O(1) 取任意子字串：
class RollingHash {
long[] hash, pow;
static final long BASE = 131L, MOD = 1_000_000_007L;
RollingHash(String s) {
int n = s.length();
hash = new long[n + 1];
pow = new long[n + 1];
pow[0] = 1;
for (int i = 0; i < n; i++) {
hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % MOD;
pow[i + 1] = pow[i] * BASE % MOD;
}
}
long get(int l, int r) { // [l, r] 閉區間
return (hash[r + 1] - hash[l] * pow[r - l + 1] % MOD + MOD) % MOD;
}
}get(l, r) 的原理：
hash[r+1] = hash[l] × p^(r-l+1) + subHash
↓
subHash = hash[r+1] - hash[l] × p^(r-l+1)就像前綴和：sum(l, r) = prefix[r+1] - prefix[l]。
雙雜湊：消滅碰撞風險
單一雜湊有碰撞問題——不同字串可能有相同雜湊值，導致誤判。實務上用兩組不同的 (BASE, MOD)：
boolean equal(int l1, int r1, int l2, int r2) {
return h1.get(l1, r1) == h1.get(l2, r2)
&& h2.get(l1, r1) == h2.get(l2, r2);
}兩個獨立雜湊同時碰撞的機率約 1 / (10⁹ × 10⁹)——競程中實際上不會發生。
應用：最長公共子字串
找兩個字串的最長公共子字串，暴力 O(n²m)，用 Rolling Hash + 二分搜尋：
二分搜尋長度 L：
若存在長度 L 的公共子字串，則更長的也值得找
→ 單調性成立，可以二分
驗證長度 L 是否可行：
對 s1 的每個長度 L 的子字串算雜湊，存入 Set
對 s2 的每個長度 L 的子字串算雜湊，查詢是否在 Set 中
→ O(n) 時間
總時間：O(n log n)Rabin-Karp 字串匹配也是同樣思路——pattern 的雜湊和滑動窗口的雜湊比較，O(n + m) 匹配，只在雜湊相同時才做 O(m) 的精確驗證。
Rolling Hash vs KMP：什麼時候選哪個
同樣是 O(n + m) 的字串匹配，兩者不是誰取代誰，而是各有各的甜蜜區：
| Rolling Hash | KMP | |
|---|---|---|
| 匹配時間 | O(n + m)（均攤） | O(n + m)（保證） |
| 多 pattern | O(n + km)，逐個算雜湊即可 | 得換 Aho-Corasick |
| 任意子字串比較 | O(1)，前綴表一建就有 | 做不到，KMP 只解「找 pattern」 |
| 碰撞風險 | 有（雙雜湊壓到近乎為零） | 無，逐字元比對不會誤判 |
一句話分：**只是要「在 text 裡找 pattern」，KMP 穩、沒有最差情況；但只要問題牽扯到「隨便切兩段子字串問它們一不一樣」，KMP 幫不上忙，Rolling Hash 的 O(1) 才是主角。**最長公共子字串就是後者——它根本不是匹配問題，是海量子字串互比。
🎬 互動視覺化：字串匹配演算法並排對比 — 把 Rabin-Karp 的滾動雜湊和 KMP 放一起跑，看雜湊值怎麼 O(1) 滑動、碰撞時又怎麼退回逐字驗證。
Rolling Hash 是一種空間換時間的預處理——把字串轉成整數的代價是一次 O(n) 建表，換來之後每次 O(1) 的子字串比較。
接下來往哪走
- 隨機化演算法：讓最壞情況消失 — 下一篇：Rolling Hash 靠隨機選 BASE 防碰撞，隨機化本身就是一門技術
- String Algorithms 字串演算法 — Rabin-Karp 的出處，KMP / Z Algorithm 這些替代方案的比較
- Prefix Sum 前綴和 & Difference Array 差分陣列 — 「前綴相減得區間」的原型，Rolling Hash 就是它的字串版