Rolling Hash

Rolling hash adalah teknik menghitung hash dari substring dengan update O(1) saat window digeser, atau query O(1) untuk substring mana pun setelah precompute prefix. Berbeda dari Chapter Rabin-Karp yang fokus pada pattern matching, Chapter ini mengeksplorasi rolling hash sebagai struktur data string serbaguna: substring equality, longest common prefix, longest repeated substring, hingga deteksi duplikasi. Kunci teknisnya adalah polynomial hash dengan mod prime besar, ditangani collision via double hash untuk safety maksimal. Pada Chapter ini kita akan membangun struktur prefix hash yang reusable dan menerapkannya pada masalah substring equality serta LCP via binary search.

Aturan: Polynomial Hash #

Untuk string S panjang n, polynomial hash didefinisikan:

text

H(S) = (S[0] * BASE^(n-1) + S[1] * BASE^(n-2) + ... + S[n-1]) mod M

BASE: bilangan > ukuran alphabet (mis. 131 untuk ASCII).
M: bilangan prima besar (Mersenne 2^61 - 1 optimal di C++ karena reduksi cepat).

Dua substring S[a..b) dan S[c..d) dengan b - a == d - c kemungkinan besar identik bila hash(a, b) == hash(c, d). Collision probability ≈ 1/M.

Mekanisme: Prefix Hash Array #

Alih-alih menghitung hash dari nol untuk setiap window, bangun prefix hash:

text

h[0] = 0
h[i + 1] = (h[i] * BASE + S[i]) mod M        untuk i = 0..n-1

Disimpan juga p[i] = BASE^i mod M. Hash substring S[l..r):

text

hash(l, r) = (h[r] - h[l] * BASE^(r-l)) mod M

Rumus ini analog dengan angka desimal: hash prefix h[r] mencakup kontribusi S[l..r) dengan bobot BASE^(r-l-1), sementara h[l] punya kontribusi yang sama tetapi digeser BASE^(r-l) posisi. Selisihnya = hash substring.

flowchart LR subgraph Prefix h H0["h[0]=0"] H1["h[1]=S0"] H2["h[2]=S0*B + S1"] HR["h[r]=S0*B^(r-1) + ... + S[r-1]"] end H2 -.dikali BASE.-> HR HR -- "minus h[l] * BASE^(r-l)" --> Sub["hash(l,r) = hash substring"]

Kode: Prefix Hash + Substring Query #

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 PrefixHash {
    std::vector<u64> h, p;
    int n;
    PrefixHash(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]));
    }
};

int main() {
    std::string S = "abababab";
    PrefixHash rh(S);
    std::cout << "S = " << S << " (n=" << S.size() << ")\n\n";

    std::cout << "Substring equality:\n";
    std::cout << "  S[0..2]==S[2..4]? "
              << (rh.hash(0, 2) == rh.hash(2, 4) ? "ya" : "tidak") << '\n';
    std::cout << "  S[0..3]==S[2..5]? "
              << (rh.hash(0, 3) == rh.hash(2, 5) ? "ya" : "tidak") << '\n';
    std::cout << "  S[0..3]==S[4..7]? "
              << (rh.hash(0, 3) == rh.hash(4, 7) ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text
S = abababab (n=8)

Substring equality:
  S[0..2]==S[2..4]? ya
  S[0..3]==S[2..5]? ya
  S[0..3]==S[4..7]? ya

p[0] = 1;: pangkat 0 dari BASE. p[i+1] = p[i] * BASE mod M.
h[i + 1] = mul_mod(h[i], BASE) + S[i]: recurrence prefix hash. Setiap karakter masuk dengan bobot yang tepat.
hash(l, r) = h[r] - h[l] * p[r - l] mod M: rumus kunci. Modulo aritmetika: pastikan sub_mod menangani kasus a < b (hasil negatif).
mul_mod dengan __uint128_t: perkalian 64×64 bit tanpa overflow. Reduksi Mersenne prime 2^61 - 1 cepat dengan shift kanan 61 bit.
Hasil ya, ya, ya: substring "ab", "aba", "aba" (lagi) di posisi berbeda semuanya identik → hash sama. Cocok dengan ekspektasi karena S = "abababab" periodik.

Aplikasi 1: Substring Equality #

Banyak masalah string memerlukan tes “apakah dua substring sama?”. Tanpa hash, dibutuhkan O(panjang substring) per query. Dengan rolling hash: O(1) per query setelah precompute O(n).

Kasus penggunaan:

Filter dokumen duplikat: bagi dokumen jadi chunk, cek apakah chunk pernah muncul di dokumen lain.
Pencarian substring berulang: deteksi musik/audio sample berulang.
Verifikasi struktur teks: cek apakah paragraf mirror pola lain.

Aplikasi 2: Longest Common Prefix via Binary Search #

LCP antara suffix S[a..] dan S[b..] dapat dicari dalam O(log n) query hash:

cpp
int lcp(const PrefixHash& rh, int a, int b) {
    int n = rh.n;
    int lo = 0, hi = n - std::max(a, b);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (rh.hash(a, a + mid) == rh.hash(b, b + mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

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 PrefixHash {
    std::vector<u64> h, p;
    int n;
    PrefixHash(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]));
    }
};

int lcp(const PrefixHash& rh, int a, int b) {
    int n = rh.n;
    int lo = 0, hi = n - std::max(a, b);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (rh.hash(a, a + mid) == rh.hash(b, b + mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

int main() {
    std::string S = "abababab";
    PrefixHash rh(S);
    std::cout << "S = " << S << '\n';
    std::cout << "LCP(S[0..], S[2..]) = " << lcp(rh, 0, 2) << '\n';
    std::cout << "LCP(S[0..], S[4..]) = " << lcp(rh, 0, 4) << '\n';
    std::cout << "LCP(S[1..], S[3..]) = " << lcp(rh, 1, 3) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
S = abababab
LCP(S[0..], S[2..]) = 6
LCP(S[0..], S[4..]) = 4
LCP(S[1..], S[3..]) = 5

int lo = 0, hi = n - std::max(a, b);: batas atas LCP — tidak bisa melebihi sisa string yang lebih pendek.
int mid = (lo + hi + 1) / 2;: pembulatan ke atas agar konvergen (hindari infinite loop ketika lo + 1 == hi).
if (rh.hash(a, a + mid) == rh.hash(b, b + mid)) lo = mid;: bila mid karakter prefix sama, coba lebih panjang. Karena hash sama sangat mungkin substring identik; collision probability kecil.
else hi = mid - 1;: bila hash berbeda pasti substring berbeda — turunkan batas atas.
Hasil: LCP S[0..] vs S[2..] = 6 (karakter "ababab"); S[0..] vs S[4..] = 4 ("abab"); S[1..] vs S[3..] = 5 ("babab").

Collision dan Double Hash #

Hash single (BASE, MOD) memiliki collision probability ≈ n / M untuk n substring. Untuk M = 2^61 - 1 dan n = 10^6, probability collision ≈ 10^6 / 2^61 ≈ 4·10^-13 — sangat aman. Tetapi untuk input adversarial (Thue-Morse sequence, anti-hash test), collision bisa dipaksa.

Solusi: double hash dengan dua pasang (BASE1, MOD1) dan (BASE2, MOD2) berbeda. Probability collision ≈ 1 / (MOD1 * MOD2) ≈ 1 / 2^122.

cpp
struct DoubleHash {
    PrefixHash 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)};
    }
};

Perbandingan pasangan hash pair<u64, u64> menggandakan biaya memori dan komputasi, tetapi collision praktis hilang. Umumnya tidak perlu verifikasi karakter eksplisit setelahnya.

Kompleksitas #

Operasi	Waktu	Ruang
Build prefix hash	`O(n)`	`O(n)`
Substring hash query	`O(1)`	—
Substring equality	`O(1)`	—
LCP via binary search	`O(log n)`	—
Longest repeated substring	`O(n log n)`	`O(n)`
Pattern matching (Rabin-Karp)	`O(n + m)` avg	`O(n + m)`

Aplikasi Lanjutan #

1. Longest Repeated Substring #

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

2. Pattern Matching (Rabin-Karp) #

Seperti Chapter sebelumnya: precompute prefix hash text, lalu bandingkan hash pattern dengan hash setiap window O(1).

3. Substring Frequency Counting #

Hitung berapa kali substring Q muncul di S: hitung hash(Q), lalu bandingkan dengan hash semua window S[i..i+|Q|). Kompleksitas O(n).

4. Palindromic Substrings #

Bangun rolling hash maju dan mundur. Substring S[l..r) palindrom bila hash_maju(l, r) == hash_mundur(n - r, n - l).

Pemilihan Parameter #

Parameter	Nilai disarankan	Catatan
`BASE`	131, 137, 91138233	Acak > ukuran alphabet
`MOD`	`2^61 - 1` Mersenne	Reduksi cepat
`MOD` alternatif	`10^9 + 7`, `10^9 + 9`	Untuk double hash
Double hash	`(131, 2^61-1)` + `(137, 10^9+7)`	Berbeda BASE dan MOD

Ringkasan #

Rolling hash memungkinkan query hash substring mana pun dalam O(1) setelah precompute prefix O(n).
Polynomial hash H = Σ s[i] * BASE^(n-1-i) mod M, dengan M = 2^61 - 1 Mersenne prime optimal untuk C++.
Prefix hash + rumus hash(l, r) = h[r] - h[l] * BASE^(r-l) mod M memberi akses O(1) ke substring hash.
Aplikasi: substring equality, LCP binary search O(log n), longest repeated substring O(n log n), pattern matching, palindromic analysis.
Collision probability sangat kecil untuk M = 2^61 - 1; double hash menambah keamanan ekstra.
Parameter disarankan: BASE = 131, MOD = 2^61 - 1; untuk input adversarial, gunakan BASE acak.