Chương trình C++ cài đặt Rolling Hash (Rabin-Karp)

Rolling Hash là hàm băm tính toán trên một cửa sổ trượt qua dữ liệu đầu vào. Ứng dụng nổi bật nhất là thuật toán tìm kiếm chuỗi Rabin-Karp.

Ý tưởng cốt lõi

Hàm băm Rabin-Karp tính giá trị số nguyên cho chuỗi:

H = c₁·aᵏ⁻¹ + c₂·aᵏ⁻² + … + cₖ·a⁰

Trong đó: a là hằng số cơ số, cᵢ là mã ký tự. Để tránh tràn số, lấy modulo n.

Khi cửa sổ trượt một ký tự, ta cập nhật hash trong O(1) thay vì tính lại từ đầu:

hash_mới = (hash_cũ - c_cũ·aᵏ⁻¹)·a + c_mới   (mod n)

Thuật toán

Bắt đầu
    Hằng P_B = 227, P_M = 1000005
    Hàm hash(s):
        r = 0
        Với i từ 0 đến s.size()-1:
            r = (r * P_B + s[i]) % P_M
        Trả về r

    Hàm rabin_karp(pattern, text):
        h1 = hash(pattern)
        h2 = 0, power = 1
        Với i từ 0 đến pattern.size()-1: power = (power * P_B) % P_M
        Với i từ 0 đến text.size()-1:
            h2 = (h2 * P_B + text[i]) % P_M
            Nếu i >= pattern.size():
                h2 = (h2 - power * text[i - pattern.size()] % P_M + P_M) % P_M
            Nếu i >= pattern.size()-1 VÀ h1 == h2:
                Trả về i - (pattern.size() - 1)  // vị trí tìm thấy
        Trả về -1  // không tìm thấy

    Nhập chuỗi text, pattern
    Nếu rabin_karp(pattern, text) == -1: in "String not found"
    Ngược lại: in vị trí tìm thấy
Kết thúc

Mã nguồn

#include <iostream>
#include <string>
using namespace std;

const int P_B = 227;
const int P_M = 1000005;

int hash(const string& s) {
    int r = 0;
    for (int i = 0; i < s.size(); i++) {
        r = r * P_B + s[i];
        r %= P_M;
    }
    return r;
}

int rabin_karp(const string& pattern, const string& text) {
    int h1 = hash(pattern);
    int h2 = 0;
    int power = 1;
    for (int i = 0; i < pattern.size(); i++)
        power = (power * P_B) % P_M;

    for (int i = 0; i < text.size(); i++) {
        h2 = h2 * P_B + text[i];
        h2 %= P_M;
        if (i >= pattern.size()) {
            h2 -= power * text[i - pattern.size()] % P_M;
            if (h2 < 0) h2 += P_M;
        }
        if (i >= pattern.size() - 1 && h1 == h2)
            return i - (pattern.size() - 1);
    }
    return -1;
}

int main() {
    string s1, s2;
    cout << "Enter Input String: "; getline(cin, s1);
    cout << "Enter String to find: "; cin >> s2;
    if (rabin_karp(s2, s1) == -1)
        cout << "String not found" << endl;
    else
        cout << "String " << s2 << " found at position " << rabin_karp(s2, s1) << endl;
    return 0;
}

Kết quả chạy

Enter Input String: Tutorialspoint
Enter String to find: a
String a found at position 6

Enter Input String: Tutorialspoint
Enter String to find: b
String not found

Phân tích độ phức tạp

• Thời gian: O(n + m) trung bình (n = độ dài text, m = độ dài pattern). Tồi nhất O(n·m) do va chạm hash (false positive) – cần kiểm tra lại chuỗi khi hash trùng.
• Không gian: O(1) bổ sung.

Lưu ý thực tế

• Chọn P_B là số nguyên tố lớn, P_M là số nguyên tố lớn (hoặc 2⁶⁴ dùng unsigned long long tràn tự nhiên).
• Để giảm va chạm, có thể dùng double hash (hai cặp P_B, P_M khác nhau) hoặc kiểm tra trực tiếp chuỗi khi hash trùng.
• C++17 có std::string_view để tránh copy chuỗi con.