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 đảm bảo O(n+m) tất định bằng cách không bao giờ lùi con trỏ text. Rabin-Karp đặt câu hỏi khác hơn: "Thay vì so từng ký tự, tại sao không so một con số đại diện cho cả cửa sổ?" Nếu hash của cửa sổ khác hash của pattern, chắc chắn không khớp — bỏ qua 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 naive. Cần cập nhật hash trong O(1) khi trượt 1 ký tự.

2. Rolling hash — cập nhật O(1)

Polynomial hash với base b và modulus q (q nguyên tố lớn):

hash(s[0..m-1]) = (s[0]·b^(m-1) + s[1]·b^(m-2) + ... + s[m-1]·b^0) mod q

Khi trượt từ cửa sổ T[i..i+m-1] sang T[i+1..i+m]:

• Bỏ ký tự trái: trừ T[i]·b^(m-1)
• Thêm ký tự phải: thêm T[i+m]·b^0 = T[i+m]
• Nhân toàn bộ với b để dịch chỉ số lên 1

Công thức rolling:

h_new = (h_old - T[i]·b^(m-1)) · b + T[i+m] (mod q)

Precompute b^(m-1) mod q một lần trước. Mỗi bước trượt: 1 phép trừ + 1 phép nhân + 1 phép cộng + 2 phép mod → O(1).

function rollingHashSearch(T, P):
    n <- T.length
    m <- P.length
    b <- 31                              -- base (số nguyên tố nhỏ, thường = kích thước bảng chữ cái)
    q <- 1_000_000_007                   -- modulus nguyên tố lớn
    bm <- b^(m-1) mod q                  -- precompute lũy thừa cao nhất
    hp <- 0                              -- hash của pattern
    hw <- 0                              -- hash của cửa sổ đầu

    -- tính hash ban đầu
    for j from 0 to m - 1:
        hp <- (hp * b + ord(P[j])) mod q
        hw <- (hw * b + ord(T[j])) mod q

    -- trượt cửa sổ
    for i from 0 to n - m:
        if hw = hp:                      -- hash khớp
            if T[i..i+m-1] = P:         -- verify ký tự (tránh spurious hit)
                báo tìm thấy tại i
        if i < n - m:                    -- cập nhật rolling hash
            hw <- (hw - (ord(T[i]) * bm) mod q + q) * b + ord(T[i+m])
            hw <- hw mod q
    return
// Time: O(n+m) trung bình  Space: O(1) ngoài kết quả

2.1 Trace nhỏ: T = "ABCAB", P = "CAB" (b=31, q=101)

Để minh hoạ, tính hash đơn giản hơn: hash(s) = (ord(s[0])·100 + ord(s[1])·10 + ord(s[2])) mod 101 (giả sử A=1, B=2, C=3).

flowchart LR
    INIT(["Tính hp, hw ban đầu"]) --> LOOP{"Còn cửa sổ?"}
    LOOP -->|"có"| CMP{"hw = hp?"}
    CMP -->|"không"| ROLL["rolling hash O(1)"]
    ROLL --> LOOP
    CMP -->|"có"| VERIFY["so ký tự T[i..i+m-1] = P?"]
    VERIFY -->|"khớp thật"| FOUND(["báo vị trí i"])
    VERIFY -->|"spurious hit"| ROLL
    FOUND --> ROLL
    LOOP -->|"hết"| DONE(["kết thúc"])

3. Spurious hit — hash collision và tại sao PHẢI verify

Spurious hit (va chạm giả) xảy ra khi hw = hp nhưng T[i..i+m-1] ≠ P. Hash function không phải injection — nhiều chuỗi có thể cùng hash value. Ví dụ với q = 101: chuỗi "abc" và "xyz" có thể cùng hash nếu (ord('a')·b² + ...) mod 101 = (ord('x')·b² + ...) mod 101.

Vì thế bước verify (so ký tự khi hash khớp) là bắt buộc — không thể bỏ vì sợ "chậm".

Ảnh hưởng lên độ phức tạp:

• Nếu số spurious hit ít (thực tế với q lớn, xác suất mỗi vị trí là 1/q ≈ 10^-9): tổng thời gian verify ≈ O(n/q · m) ≈ O(1) → tổng O(n+m).
• Worst-case: mọi cửa sổ đều là spurious hit → verify O(m) cho từng trong O(n) cửa sổ → O(n·m).

Worst-case này xảy ra khi chọn q quá nhỏ hoặc chuỗi đặc biệt. Trong thực tế, chọn q nguyên tố lớn (10^9+7) làm xác suất collision rất thấp.

4. Ưu thế đa mẫu — điểm mạnh độc đáo của Rabin-Karp

Đây là lý do chính Rabin-Karp vẫn được dùng dù KMP đảm bảo worst-case tốt hơn.

Bài toán: Cho k pattern P1, P2, ..., Pk cùng độ dài m và một text T dài n. Tìm tất cả vị trí xuất hiện của bất kỳ pattern nào.

KMP/naive cho đa mẫu: phải chạy k lần qua text → O(k·n + k·m).

Rabin-Karp cho đa mẫu:

1. Tính hash của k pattern, bỏ vào một Set H — O(k·m).
2. Quét text một lần: với mỗi cửa sổ, kiểm tra hw ∈ H trong O(1).
3. Chỉ verify ký tự khi có hash match → O(1) trung bình mỗi cửa sổ.
4. Tổng: O(k·m + n) — không phụ thuộc k trong bước quét text.

function rabinKarpMulti(T, patterns):   -- tất cả pattern cùng độ dài m
    m <- patterns[0].length
    b <- 31
    q <- 1_000_000_007
    bm <- b^(m-1) mod q

    -- bước 1: hash tất cả pattern vào Set
    patternHashes <- Set rỗng
    for each P in patterns:
        hp <- 0
        for j from 0 to m - 1:
            hp <- (hp * b + ord(P[j])) mod q
        patternHashes.add(hp)

    -- bước 2: quét text một lần
    hw <- 0
    for j from 0 to m - 1:             -- hash cửa sổ đầu
        hw <- (hw * b + ord(T[j])) mod q

    results <- danh sách rỗng
    for i from 0 to n - m:
        if hw ∈ patternHashes:          -- kiểm tra O(1) với Set/hash-table
            for each P in patterns:     -- verify pattern nào khớp thật
                if T[i..i+m-1] = P:
                    thêm (i, P) vào results
        if i < n - m:
            hw <- ((hw - (ord(T[i]) * bm) mod q + q) * b + ord(T[i+m])) mod q
    return results
// Time: O(k·m + n) trung bình  Space: O(k)

So sánh ba hướng tiếp cận đa mẫu:

Rabin-Karp và Aho-Corasick có cùng asymptotic, nhưng Rabin-Karp đơn giản hơn nhiều để cài đặt. Aho-Corasick đảm bảo worst-case còn Rabin-Karp chỉ đảm bảo trung bình.

5. So sánh Rabin-Karp và KMP

KMP là lựa chọn tốt khi cần đảm bảo tuyệt đối. Rabin-Karp là lựa chọn thực dụng khi tìm đa mẫu hoặc cần triển khai nhanh.

6. Pitfall

Pitfall 1 — Bỏ bước verify khi hash khớp

-- SAI: tin vào hash, không verify
if hw = hp:
    báo tìm thấy tại i    -- có thể là spurious hit!

-- ĐÚNG: luôn verify bằng so ký tự
if hw = hp:
    if T[i..i+m-1] = P:
        báo tìm thấy tại i

Bỏ verify dẫn đến báo vị trí sai (false positive). Với q nhỏ hoặc dữ liệu đặc biệt, tỉ lệ false positive có thể rất cao. Rabin-Karp là thuật toán xác suất đúng (không báo false negative), không phải tất định — luôn phải verify.

Pitfall 2 — Quên + q trước phép mod khi trừ

-- SAI: kết quả có thể âm khi hw < T[i]*bm mod q
hw <- ((hw - ord(T[i]) * bm) * b + ord(T[i+m])) mod q

-- ĐÚNG: cộng q để đảm bảo không âm trước mod
hw <- ((hw - (ord(T[i]) * bm) mod q + q) * b + ord(T[i+m])) mod q

Trong nhiều ngôn ngữ, phép mod với số âm trả về giá trị âm (ví dụ: -3 mod 5 = -3 trong Python). Cộng thêm q trước khi mod đảm bảo kết quả luôn không âm.

Pitfall 3 — Dùng q quá nhỏ dẫn đến collision nhiều

-- SAI: q nhỏ → nhiều collision → verify thường xuyên → thực ra O(n·m)
q <- 101   -- chỉ 101 giá trị hash khác nhau!

-- ĐÚNG: q nguyên tố lớn
q <- 1_000_000_007   -- ~10^9 giá trị, xác suất collision ~10^-9/cửa sổ

Với q=101 và n=10^6 cửa sổ, trung bình ~10^4 spurious hit — verify 10^4 lần × O(m) = tốn kém. Với q=10^9+7, chỉ ~10^-3 spurious hit trung bình cho cả quá trình.

7. Liên hệ các bài khác

• KMP — failure function & matching O(n+m): Tiếp cận tất định so với xác suất của Rabin-Karp. KMP không có rủi ro collision nhưng khó mở rộng cho đa mẫu; Rabin-Karp mở rộng tự nhiên qua hash set.
• Naive string matching: Cả hai đều trượt cửa sổ qua text; điểm khác biệt là Rabin-Karp dùng hash để bỏ qua nhanh các vị trí không khớp thay vì so ký tự từng bước.
• Aho-Corasick: Giải cùng bài toán đa mẫu nhưng theo hướng automaton — xây trie + failure link, tất định O(n + số kết quả). Khi k pattern lớn và cần đảm bảo worst-case, Aho-Corasick thay thế Rabin-Karp.
• Hash function — nền tảng: Polynomial hash (Rabin fingerprint) là trường hợp đặc biệt của hash function tổng quát — nên đọc để hiểu tại sao chọn base và modulus nguyên tố.

📚 Deep Dive

Tóm tắt

• Rabin-Karp so hash của cửa sổ trượt thay vì so từng ký tự — chỉ verify ký tự khi hash khớp.
• Rolling hash cập nhật O(1) khi trượt 1 ký tự: h_new = (h_old - T[i]·b^(m-1))·b + T[i+m] (mod q).
• Spurious hit (hash trùng, chuỗi khác) là không thể tránh hoàn toàn — bước verify bằng so ký tự là bắt buộc.
• Trung bình O(n+m); worst-case O(n·m) khi nhiều collision — chọn q nguyên tố lớn để giảm thiểu.
• Ưu thế đa mẫu: k pattern cùng độ dài m → hash vào Set, quét text một lần O(n) — tổng O(k·m + n), độc lập k trong bước quét.
• Double hashing (hai cặp b, q) giảm xác suất collision xuống ~1/q² — đủ an toàn cho ứng dụng thực tế.

Tự kiểm tra

Bài tiếp theo: Z-function — z-array và ứng dụng