Rabin-Karp: rolling hash cho đa mẫu

TL;DR: Rabin-Karp thay việc so từng ký tự bằng so hash của cửa sổ trượt. Rolling hash cập nhật trong O(1) khi trượt một ký tự: bỏ ký tự trái, thêm ký tự phải. Khi hash khớp, mới so ký tự để xác nhận (tránh "spurious hit", hash trùng nhưng chuỗi khác). Trung bình O(n+m); worst-case O(n·m) khi nhiều collision. Ưu thế lớn nhất: tìm k pattern cùng độ dài chỉ cần một lần quét text, hash k pattern vào Set, mỗi cửa sổ kiểm tra O(1) thay vì O(k·m).

KMP ở bài trước luôn O(n+m) vì không lùi con trỏ text. Rabin-Karp đổi chỗ so: nếu hash của cửa sổ khác hash của pattern thì bỏ qua cửa sổ đó mà không so ký tự nào. Nếu hash bằng nhau, xác suất cao là khớp thật, chỉ cần verify lại.

1. Ý tưởng: so hash thay vì so ký tự

Giả sử ta có hàm hash(s) trả về một số nguyên dương cho mỗi chuỗi s. Khi trượt cửa sổ dài m qua text:

1. Tính hp = hash(P), hash của pattern, tính một lần.
2. Tính hw = hash(T[0..m-1]), hash của cửa sổ đầu tiên.
3. Với mỗi bước trượt: nếu hw ≠ hp → bỏ qua (không so ký tự). Nếu hw = hp → so ký tự để xác nhận.
4. Cập nhật hw cho cửa sổ kế tiếp, đây là chỗ rolling hash phát huy.

Vấn đề: nếu mỗi bước tính lại hash(T[i..i+m-1]) từ đầu thì mất O(m), tổng O(n·m), không khác gì naive. Cần cập nhật hash trong O(1) khi trượt 1 ký tự.