Băm xâu (String hashing) — polynomial rolling hash

Với xâu `s = "abcab"`, ánh xạ `a→1, b→2, c→3`, chọn cơ số `b = 31`, modulo `p = 101` (modulo NHỎ, chỉ để tính tay minh họa cơ chế — bài thật luôn dùng modulo lớn cỡ `10^9`, xem callout bên dưới). Với quy ước `h[0] = 0`, công thức truy hồi `h[i] = h[i-1]·b + giá_trị(s[i]) mod p`.

Hai mảng `h` và `pw` được tính song song trong cùng một vòng lặp `O(n)`: ```python def tien_xu_ly_hash(s, base, mod): """Tinh mang hash tien to h[0..n] va mang luy thua pw[0..n] cua base modulo mod. h[i] = hash cua tien to do dai i (s[0..i-1], 0-indexed trong Python); h[0] = 0. Ky tu duoc anh xa a=1..z=26 de tranh hash('') == hash('aaa...').""" n = len(s) h = [0] * (n + 1) pw = [1] * (n + 1) for i in range(1, n + 1): h[i] = (h[i - 1] * base + (ord(s[i - 1]) - ord("a") + 1)) % mod pw[i] = (pw[i - 1] * base) % mod return h, pw ```

Hàm `getHash(l, r)` lấy hash một đoạn con bất kỳ (1-indexed) chỉ bằng một phép trừ và một phép nhân, không quét lại xâu: ```python def get_hash(h, pw, mod, l, r): """Hash cua doan con s[l..r] (1-indexed, tinh ca hai dau) trong O(1), dung mang h va pw da tien xu ly: hash(l,r) = h[r] - h[l-1]*b^(r-l+1).""" return (h[r] - h[l - 1] * pw[r - l + 1]) % mod ``` và hàm so sánh hai đoạn dùng lại `getHash` hai lần: ```python def so_sanh_doan_bang_hash(l1, r1, l2, r2, h, pw, mod): """Hai doan con [l1,r1] va [l2,r2] co bang nhau khong -- O(1) sau tien xu ly, thay vi so tung ky tu O(do dai doan).""" if r1 - l1 != r2 - l2: return False return get_hash(h, pw, mod, l1, r1) == get_hash(h, pw, mod, l2, r2) ```

Ta cần so sánh đoạn `s[1..2] = "ab"` với đoạn `s[4..5] = "ab"`. Áp dụng công thức `hash(l,r) = h[r] - h[l-1]·pw[r-l+1] mod p`: với `(l,r)=(1,2)`, `hash = h[2] - h[0]·pw[2] = 33 - 0 = 33`. Với `(l,r)=(4,5)`, `hash = h[5] - h[3]·pw[2] = 57 - 16·52 = 57 - 832 ≡ 33 (mod 101)`. Hai giá trị bằng nhau (đều bằng 33), và quan sát trực tiếp cũng xác nhận `s[1..2] = s[4..5] = "ab"`. Vậy hai đoạn con bằng nhau, kết luận đạt được chỉ bằng phép toán trên mảng đã tiền xử lý, không quét lại xâu.

Bài chuẩn dừng ở nhận biết bằng mắt một chuỗi có "lặp lại" hay không với xâu ngắn. Đề HSG cho xâu dài đến `10^5`–`10^6` ký tự và yêu cầu chỉ RA con số chu kỳ nhỏ nhất chính xác, với nhiều xâu cần kiểm tra — buộc phải có thuật toán, không còn "nhìn là thấy".

Thử lần lượt mọi ước số `k` của `n` theo thứ tự tăng dần. Với mỗi `k`, kiểm tra `s[1..n-k] = s[k+1..n]` bằng MỘT lần so sánh hash — đúng ngay lập tức `k` đó là chu kỳ nhỏ nhất (vì ta thử theo thứ tự tăng dần). Nếu không ước nào thỏa (trừ chính `n`), xâu không có chu kỳ thực sự nào khác chính nó.

Chỉ cần một vòng lặp qua các ước của `n`, mỗi bước gọi `getHash` hai lần: ```python def chu_ky_nho_nhat_hash(s, h, pw, mod): """Chu ky nho nhat k (1<=k<=n, n chia het k) sao cho s[i]==s[i+k] voi moi i hop le -- thu tung uoc k cua n theo thu tu tang dan, kiem tra bang MOT lan so sanh hash s[1..n-k] voi s[k+1..n].""" n = len(s) for k in range(1, n + 1): if n % k != 0: continue if k == n: return k if get_hash(h, pw, mod, 1, n - k) == get_hash(h, pw, mod, k + 1, n): return k return n ```

Với `s = "abcabcabc"` (`n = 9`), các ước của 9 theo thứ tự tăng là 1, 3, 9. Với `k=1`: so `s[1..8]="abcabcab"` với `s[2..9]="bcabcabc"` — khác nhau, loại. Với `k=3`: so `s[1..6]="abcabc"` với `s[4..9]="abcabc"` — BẰNG NHAU. Vậy chu kỳ nhỏ nhất của `"abcabcabc"` là `k=3`, đúng như quan sát trực tiếp (xâu là "abc" lặp 3 lần).

Bài chuẩn không cần lo về đụng độ hash vì hiếm khi kiểm tra nghiêm ngặt. Đề HSG QG thường có bộ test chuyên biệt (test chống hash) được thiết kế để hai xâu KHÁC NHAU cho cùng một giá trị hash đơn — nếu lời giải chỉ dùng một cặp `(b, p)`, bài sẽ sai ở đúng bộ test đó dù thuật toán về nguyên lý là đúng.

Tìm một cặp đụng độ cụ thể bằng cách duyệt hết `2^6=64` xâu độ dài 6 trên bảng chữ 'a','b' với modulo nhỏ `p=31` (minh họa, không phải giá trị dùng khi thi) — dừng ngay khi gặp hai xâu khác nhau cùng hash: ```python def tim_va_cham_hash_don(mod_nho, base_nho, do_dai): """Minh hoa NGUYEN LY DIRICHLET: voi bang chu 'ab' va do_dai ky tu co 2^do_dai xau phan biet. Neu mod_nho < 2^do_dai, duyet HET moi xau chac chan gap it nhat mot cap trung hash -- day la LY DO CAN double hashing, khong phai vi du ngau nhien.""" bang = {} for to_hop in itertools.product("ab", repeat=do_dai): s = "".join(to_hop) h, _ = tien_xu_ly_hash(s, base_nho, mod_nho) key = h[do_dai] if key in bang and bang[key] != s: return bang[key], s bang[key] = s return None ```

Chạy hàm trên cho ra cặp `s1 = "aaaaaa"` và `s2 = "aaaaba"` — hai xâu khác nhau (khác ở ký tự thứ 5), nhưng với `base=31, mod=31` cả hai đều có `hash = 1`.

Dùng HAI cặp `(base, mod)` độc lập, coi một đoạn "có thể bằng nhau" chỉ khi CẢ HAI thành phần hash đều trùng: ```python def hash_kep(s): """Mo rong danh cho HSG: hai cap (base, mod) DOC LAP -- tra ve bo 4 mang de tinh hash kep cua bat ky doan con nao.""" h1, pw1 = tien_xu_ly_hash(s, BASE1, MOD1) h2, pw2 = tien_xu_ly_hash(s, BASE2, MOD2) return h1, pw1, h2, pw2 ``` ```python def get_hash_kep(h1, pw1, h2, pw2, l, r): """Cap (hash1, hash2) cua doan [l,r] -- hai doan chi duoc coi la 'co the bang nhau' khi CA HAI thanh phan trung nhau.""" return (get_hash(h1, pw1, MOD1, l, r), get_hash(h2, pw2, MOD2, l, r)) ```

Với `base1=131, mod1≈10^9+7` và `base2=137, mod2≈998244353`, cặp hash kép của `"aaaaaa"` là `(876254690, 700861134)`, còn của `"aaaaba"` là `(876254821, 700861271)` — hai cặp này KHÁC NHAU ở cả hai thành phần.

Xét `s_1="aaaaaa"` và `s_2="aaaaba"`. Theo hash đơn với `base=31, mod=31`: `hash(s_1)=hash(s_2)=1` — đụng độ thật sự (1), không phải giả định. Theo hash kép với hai modulo lớn: `hash_kép(s_1)=(876254690, 700861134) ≠ (876254821, 700861271)=hash_kép(s_2)` (2). Từ (1) và (2) suy ra: modulo nhỏ làm lộ đụng độ mà modulo lớn và double hashing đều tránh được. Vậy double hashing chỉ cần thiết khi đề có khả năng chứa test chống hash (n lớn, đề công khai là dạng thi đấu) — với modulo cỡ `10^9` đơn lẻ, xác suất đụng độ ngẫu nhiên đã cực nhỏ cho dữ liệu KHÔNG cố ý; double hashing chỉ thêm hằng số thời gian gấp đôi để đổi lấy an toàn trước test cố ý.