Rolling Hash — Substring Fingerprints

Ý tưởng

So sánh hai đoạn con trực tiếp mất O(độ dài). Băm đa thức: coi xâu là số cơ số B, lấy phần dư MOD:

h(s) = s[0]·B^(k−1) + s[1]·B^(k−2) + ... + s[k−1]

Tiền tố H[i] = hash của s[0..i); đoạn (l, r] = H[r] − H[l]·B^(r−l). Chuẩn bị O(n), mỗi truy vấn O(1):

const long long MOD = 1000000007;   // hoặc 2^61 − 1 (Mersenne)
const long long B = 131;
vector<long long> H(n + 1, 0), P(n + 1, 1);
for (int i = 0; i < n; ++i) {
    H[i+1] = (H[i] * B + s[i]) % MOD;
    P[i+1] = P[i] * B % MOD;
}
// hash của s[l..r) = (H[r] - H[l]*P[r-l] % MOD + MOD) % MOD

SỐ ÂM sau phép trừ: +MOD rồi %MOD — bẫy số âm module trước đã học.

Va chạm — câu chuyện thật

Hai xâu khác nhau có thể trùng hash: xác suất ~1/MOD mỗi cặp. Với MOD = 10^9+7 và 10^6 cặp so sánh: kỳ vọng va chạm ~10^6/10^9 = 10^3 — NHỎ nhưng không phải không; kẻ địch CỐ TÌNH (hack) thì tìm được cặp chống đơn-băm dễ dàng. Giải pháp contest: HAI băm (MOD, B khác nhau), so sánh CẢ HAI:

// pair<hash1, hash2> — va chạm đồng thời ~1/(MOD1·MOD2) ≈ 10^-18

Đề "chống băm" ở HSG thật: các bộ test sinh để hạ đơn-băm nhỏ — băm kép là phao chuẩn.

Ứng dụng kinh điển — tiền tố đối xứng

Tiền tố s[0..k) là palindrome ⇔ s[0..k) == reverse(s[0..k)). Precompute hash của xâu và xâu ĐẢO; nhị phân tìm tiền tố đối xứng dài nhất (tiền tố đối xứng của độ dài k+1... không đơn điệu? — ĐÚNG đơn điệu: nếu tiền tố k đối xứng thì tiền tố k−1 cũng vậy? KHÔNG! "abcb a"? — s = "abcba": tiền tố 5 đối xứng, tiền tố 4 "abcb" không, tiền tố 3 "abc" không... tiền tố 1 "a" có. Đơn điệu SAI — phải quét mọi k hoặc rút ra từManacher (chưa học). Quét O(n) với hash từng k vẫn nhanh.)

Đếm xâu con phân biệt

Số xâu con phân biệt của s (n ≤ 1000): mọi cặp (độ dài, vị trí) — với MỖI độ dài L, thu thập hash của n−L+1 đoạn, sort, đếm khác nhau. Tổng O(n² log n) — n = 1000: ~10^7, ổn. n = 10^5: chết (cần suffix array / automaton — để sau). Biết GIỚI HÀN của công cụ mình đang cầm.

Điểm mấu chốt: băm tiền tố = so sánh O(1); băm kép chống va chạm; số âm +MOD; đếm xâu con phân biệt O(n² log n) tới n ≈ 1000.