字串不能直接拿來當陣列的 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 是一種空間換時間的預處理——把字串轉成整數的代價是一次 O(n) 建表，換來之後每次 O(1) 的子字串比較。