Algoritma Rabin-Karp menyelesaikan string matching dengan pendekatan berbeda dari KMP atau Z: alih-alih membandingkan karakter, ia membandingkan hash dari pattern dengan hash setiap window text. Karena hash window bisa diperbarui dalam waktu O(1) dengan teknik rolling hash, algoritma ini rata-rata O(n + m). Rabin-Karp juga secara natural memperluas ke pencarian banyak pattern sekaligus — cukup bandingkan hash window dengan hash dari semua pattern. Pada Chapter ini kita akan memahami rolling hash polynomial, membangun struktur prefix hash untuk akses O(1) ke substring apapun, dan menerapkannya pada search maupun substring equality.

Aturan: Bandingkan Hash, Bukan Karakter #

Rabin-Karp menggunakan polynomial rolling hash:

text 
H(s) = (s[0] * BASE^(m-1) + s[1] * BASE^(m-2) + ... + s[m-1]) mod M
  • BASE: konstanta > ukuran alphabet (mis. 131 untuk ASCII).
  • M: bilangan prima besar (mis. 2^61 - 1 Mersenne prime).
  • Hash window T[i..i+m-1] dapat dihitung dari hash window sebelumnya T[i-1..i+m-2] dalam O(1).

Mekanisme: Rolling Hash #

Misal H_i = hash(T[i..i+m-1]). Maka:

text 
H_{i+1} = ((H_i - T[i] * BASE^(m-1)) * BASE + T[i+m]) mod M
  • Kurangi kontribusi karakter kiri yang keluar (T[i]).
  • Geser sisanya satu posisi (kali BASE).
  • Tambahkan karakter kanan baru (T[i+m]).
  • Ambil modulo M setiap langkah.

Bila hash window sama dengan hash pattern, lakukan verifikasi karakter per karakter untuk menyingkirkan spurious hit (false positive akibat collision).

Kode: Rolling Hash dengan Prefix Array #

Alih-alih menggeser hash satu per satu, lebih fleksibel membangun prefix hash h[i] = hash(T[0..i-1]). Hash substring T[l..r) dapat diakses dalam O(1):

text 
hash(T[l..r)) = h[r] - h[l] * BASE^(r-l)  mod M
cpp 
#include <iostream>
#include <string>
#include <vector>

typedef unsigned long long u64;
const u64 MOD = (1ULL << 61) - 1;   // Mersenne prime
const u64 BASE = 131;

u64 mul_mod(u64 a, u64 b) {
    __uint128_t r = (__uint128_t)a * b;
    u64 lo = (u64)r;
    u64 hi = (u64)(r >> 64);
    lo = (lo & MOD) + (lo >> 61) + (hi << 3);
    if (lo >= MOD) lo -= MOD;
    return lo;
}

u64 add_mod(u64 a, u64 b) {
    u64 r = a + b;
    if (r >= MOD) r -= MOD;
    return r;
}

u64 sub_mod(u64 a, u64 b) {
    return a >= b ? a - b : a + MOD - b;
}

struct RollingHash {
    std::vector<u64> h;  // prefix hash
    std::vector<u64> p;  // powers of BASE
    int n;

    RollingHash(const std::string& s) {
        n = static_cast<int>(s.size());
        h.assign(n + 1, 0);
        p.assign(n + 1, 0);
        p[0] = 1;
        for (int i = 0; i < n; ++i) {
            p[i + 1] = mul_mod(p[i], BASE);
            h[i + 1] = add_mod(mul_mod(h[i], BASE), (u64)(unsigned char)s[i]);
        }
    }

    u64 hash(int l, int r) const {
        u64 a = h[r];
        u64 b = mul_mod(h[l], p[r - l]);
        return sub_mod(a, b);
    }
};

int main() {
    std::string S = "abcabcabc";
    RollingHash rh(S);
    std::cout << "S = " << S << '\n';
    std::cout << "hash(0,3) == hash(3,6)? "
              << (rh.hash(0, 3) == rh.hash(3, 6) ? "ya" : "tidak") << '\n';
    std::cout << "hash(0,3) == hash(1,4)? "
              << (rh.hash(0, 3) == rh.hash(1, 4) ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
S = abcabcabc
hash(0,3) == hash(3,6)? ya
hash(0,3) == hash(1,4)? tidak
  1. MOD = (1ULL << 61) - 1: Mersenne prime 2^61 - 1. Operasi modulo dapat dioptimasi dengan bit-shift (lihat mul_mod).
  2. p[i] = BASE^i mod M: precompute pangkat BASE. Diperlukan untuk rumus hash substring.
  3. h[i + 1] = mul_mod(h[i], BASE) + s[i]: recurrence prefix hash. h[i] adalah hash s[0..i-1].
  4. mul_mod dengan __uint128_t: mengalikan dua bilangan 64-bit tanpa overflow. Untuk Mersenne prime, reduksi cepat dengan shift.
  5. hash(l, r) = sub_mod(h[r], mul_mod(h[l], p[r - l])): hash substring s[l..r). Bila sama untuk dua substring → kemungkinan besar substring sama (collision sangat jarang untuk M = 2^61 - 1).
  6. Hasil: "abc" == "abc" (hash sama). "abc" != "bca" (hash berbeda).
cpp 
#include <iostream>
#include <string>
#include <vector>

typedef unsigned long long u64;
const u64 MOD = (1ULL << 61) - 1;
const u64 BASE = 131;

u64 mul_mod(u64 a, u64 b) {
    __uint128_t r = (__uint128_t)a * b;
    u64 lo = (u64)r;
    u64 hi = (u64)(r >> 64);
    lo = (lo & MOD) + (lo >> 61) + (hi << 3);
    if (lo >= MOD) lo -= MOD;
    return lo;
}
u64 add_mod(u64 a, u64 b) { u64 r = a + b; if (r >= MOD) r -= MOD; return r; }
u64 sub_mod(u64 a, u64 b) { return a >= b ? a - b : a + MOD - b; }

struct RollingHash {
    std::vector<u64> h, p;
    int n;
    RollingHash(const std::string& s) {
        n = static_cast<int>(s.size());
        h.assign(n + 1, 0);
        p.assign(n + 1, 0);
        p[0] = 1;
        for (int i = 0; i < n; ++i) {
            p[i + 1] = mul_mod(p[i], BASE);
            h[i + 1] = add_mod(mul_mod(h[i], BASE), (u64)(unsigned char)s[i]);
        }
    }
    u64 hash(int l, int r) const {
        return sub_mod(h[r], mul_mod(h[l], p[r - l]));
    }
};

std::vector<int> rabin_karp(const std::string& T, const std::string& P) {
    int n = static_cast<int>(T.size());
    int m = static_cast<int>(P.size());
    std::vector<int> result;
    if (m == 0 || m > n) return result;

    RollingHash rh_T(T), rh_P(P);
    u64 hp = rh_P.hash(0, m);

    for (int i = 0; i + m <= n; ++i) {
        if (rh_T.hash(i, i + m) == hp) {
            bool match = true;
            for (int j = 0; j < m; ++j) {
                if (T[i + j] != P[j]) { match = false; break; }
            }
            if (match) result.push_back(i);
        }
    }
    return result;
}

int main() {
    std::string T = "GEEKS FOR GEEKS";
    std::string P = "GEEK";

    auto occ = rabin_karp(T, P);
    std::cout << "T = " << T << '\n';
    std::cout << "P = " << P << '\n';
    std::cout << "Indeks: ";
    for (int idx : occ) std::cout << idx << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
T = GEEKS FOR GEEKS
P = GEEK
Indeks: 0 10
  1. u64 hp = rh_P.hash(0, m);: hash pattern dihitung sekali. Bandingkan dengan hash setiap window text.
  2. rh_T.hash(i, i + m) == hp: cek hash window di T[i..i+m). Bila sama, kandidat occurrence.
  3. Verifikasi karakter per karakter: cek langsung T[i + j] == P[j]. Diperlukan karena ada kemungkinan spurious hit (collision). Untuk M = 2^61 - 1, collision probability ~n/M — sangat kecil untuk input praktis.
  4. Indeks 0 dan 10: dua kemunculan "GEEK" di "GEEKS FOR GEEKS".

Kompleksitas #

TahapBest/AverageWorst
Precompute hash patternO(m)O(m)
Precompute prefix hash textO(n)O(n)
Scan window + verifyO(n + m)O(n·m)

Worst case O(n·m) terjadi ketika banyak spurious hit. Contoh adversarial: T = "AAAAAAAA", P = "AAA" — hash cocok di setiap window, verifikasi penuh m karakter setiap kali. Average case (input acak): collision sangat jarang, verifikasi O(1) expected → total O(n + m).

Collision dan Double Hashing #

Bila tetap khawatir collision, gunakan double hash dengan dua pasangan (BASE1, MOD1) dan (BASE2, MOD2) berbeda. Probability collision = 1 / (MOD1 * MOD2) ≈ 1 / 2^122.

cpp 
struct DoubleHash {
    RollingHash h1, h2;
    DoubleHash(const std::string& s) : h1(s, BASE1, MOD1), h2(s, BASE2, MOD2) {}
    std::pair<u64, u64> hash(int l, int r) const {
        return {h1.hash(l, r), h2.hash(l, r)};
    }
};

Dua hash sekaligus menjamin tidak ada collision praktis; tidak perlu verifikasi karakter.

Aplikasi Lanjutan #

1. Substring Equality #

Dua substring s[l1..r1) dan s[l2..r2) sama bila r1 - l1 == r2 - l2 dan hash(l1, r1) == hash(l2, r2). Banyak masalah string (longest common prefix, repeated substring) selesai dengan ini dalam O(1) per query.

2. Multiple Pattern Matching #

Bangun hash setiap pattern, simpan di hash set. Saat scanning text, cek apakah hash window ada di set. Kompleksitas O(n + k) untuk k pattern (rata-rata).

3. Plagiarism Detection #

Bagi dokumen menjadi chunk berukuran m byte, hash setiap chunk, lalu bandingkan antar dokumen via hash table.

4. Longest Repeated Substring (Binary Search + Hash) #

Binary search panjang L, lalu cek apakah ada dua substring berbeda panjang L dengan hash sama. O(n log n).

Perbandingan dengan KMP #

AspekKMPRabin-Karp
Worst caseO(n + m)O(n·m) (collision)
Average caseO(n + m)O(n + m)
Multi-patternTidak langsungYa (hash set)
Substring queryTidakYa (O(1) per query)
MemoriO(m)O(n + m) (prefix array)
ImplementasiLoop whileAritmetika modular

Pilih KMP bila butuh guaranteed linear dan hanya search. Pilih Rabin-Karp bila butuh substring query berulang atau multi-pattern.

Ringkasan #

  • Rabin-Karp menggunakan polynomial rolling hash untuk membandingkan pattern dengan window text.
  • Hash window dapat diupdate dalam O(1) (sliding) atau diakses dalam O(1) dengan prefix hash array.
  • Average case O(n + m); worst case O(n·m) karena spurious hit — verifikasi karakter wajib.
  • Pilihan BASE = 131, MOD = 2^61 - 1 Mersenne prime memberi collision probability sangat kecil.
  • Double hash dengan dua (BASE, MOD) berbeda menghilangkan kebutuhan verifikasi.
  • Aplikasi: substring equality, multiple pattern, plagiarism detection, longest repeated substring (binary search + hash).
  • Lebih fleksibel dari KMP untuk masalah substring query; tidak menjamin worst case linear seperti KMP.