Rabin-Karp

Dizeler O(n + m) avg O(1)

Deseni ve her metin penceresini yuvarlanan bir hash ile hashler; yalnızca hash'ler çakıştığında karakter karakter doğrular.

text

E10

K11

S12

pattern

MetinDesen

patHash=22052winHash=22052

1/31

Desen özeti ve ilk pencerenin özeti ön hesaplanıyor.

DeğişmezPencere özeti, o m karakterin özetine eşittir. Eşit özetler yine farklı olabilir, bu yüzden isabet doğrulanır; farklı özetler asla eşleşemez, bu yüzden ıskalama bedavaya gelir.

işaretçieşleşmeuyumsuzpencere

rabin-karp.c

#define BASE 256
#define MOD 1000000007
 
void rabinKarp(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    long ph = 0, th = 0, pow = 1;
    for (int i = 0; i < m; i++) {
        ph = (ph * BASE + p[i]) % MOD;
        th = (th * BASE + t[i]) % MOD;
        if (i) pow = (pow * BASE) % MOD;
    }
    for (int i = 0; i + m <= n; i++) {
        if (ph == th) {
            int k = 0;
            while (k < m && t[i + k] == p[k]) k++;
            if (k == m) printf("found at %d\n", i);
        }
        if (i + m < n) {
            th = ((th - t[i] * pow) * BASE
                  + t[i + m]) % MOD;
            if (th < 0) th += MOD;
        }
    }
}

Rabin-Karp nasıl çalışır?

Dizeleri değil hash'leri karşılaştır: yuvarlanan hash, pencere kayarken değerini O(1)'de günceller. Yalnızca hash çakışması gerçek karakter karşılaştırması tetikler.

En iyi durum

Az çakışma: beklenen O(n + m).

En kötü durum

Düşmanca çakışmalar: O(n·m).

Ne zaman kullanılır?

Çoklu desen arama (tek hash kümesi, çok desen), intihal parça eşleme.