Lesson 40 — String Matching & Rabin-Karp
Ba module tương tác: (1) Naive matching đếm phép so sánh; (2) Rolling hash cập nhật O(1); (3) Rabin-Karp so hash + verify, highlight false positive.
1. Naive matching — trượt & so từng ký tự
Vị trí i: 0
So sánh: 0
Khớp tại: —
Nhấn "Bước tiếp" để đặt pattern tại i=0 và so từng ký tự.
Mỗi lần lệch → dịch pattern sang phải 1 ô, so lại từ đầu pattern. Worst-case O(n·m).
2. Rolling hash — cập nhật O(1) khi trượt
Nhấn "Trượt window" để khởi tạo hash của window đầu tiên.
b = 256, q = 101 (nhỏ để dễ đọc). Công thức trượt: hnew = ((hold − T[i]·b^(m-1))·b + T[i+m]) mod q. Đỏ = bỏ ký tự trái, xanh = thêm ký tự phải.
3. Rabin-Karp — so hash trước, verify khi khớp
hash(P): —
hash(window): —
Verify: 0
False positive: 0
Nhấn "Bước tiếp". Vàng = hash trùng nhưng chuỗi khác (false positive); xanh = khớp thật.
q nhỏ (101) cố tình tạo false positive để bạn thấy vì sao phải verify. q ~10⁹ thật thì gần như không có.