Rabin-Karp

Rabin-Karp hash tabanlı string eşleme öğrenirsin.

Rabin-Karp

Rabin-Karp, hash tabanlı bir string eşleme algoritmasıdır. Örüntünün ve metindeki her pencerenin hash değerini karşılaştırır.

Hash'ler eşitse olası eşleşme vardır; tam doğrulama için karakter karakter karşılaştırma yapılır. Hash çakışmaları bu doğrulama adımıyla çözülür.

Yuvarlanan hash (rolling hash) sayesinde bir pencereden diğerine O(1) sürede geçilir; toplam karmaşıklık ortalama O(n+m)'dir.

Yuvarlanan hash

Yuvarlanan hash, pencere sağa kaydırıldığında eski karakterin katkısını çıkarıp yeni karakterin katkısını ekler. Bu, hash'i baştan hesaplamaktan kaçınır.

Formül: h = ((h - ord(text[i-m]) * pow_base) * base + ord(text[i])) % mod. Burada pow_base = base^(m-1) mod mod'dir.

Mod alınması büyük sayı taşmasını önler; mod değeri genellikle büyük bir asal sayı seçilir.

Uygulama rabin_karp fonksiyonu

rabin_karp(text, pattern) yaz. İlk eşleşme indeksini döndür; yoksa -1. print(rabin_karp("merhabatarif", "tarif")) ile 7 yazdır.

Örnek çözümü göster

def rabin_karp(text, pattern):
    # Hash tabanlı eşleşme
    base = 256
    mod = 101
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return -1
    ph = 0
    th = 0
    pow_base = 1
    for _ in range(m - 1):
        pow_base = (pow_base * base) % mod
    for i in range(m):
        ph = (ph * base + ord(pattern[i])) % mod
        th = (th * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if ph == th:
            if text[i:i + m] == pattern:
                return i
        if i < n - m:
            th = ((th - ord(text[i]) * pow_base) * base + ord(text[i + m])) % mod
            if th < 0:
                th += mod
    return -1
print(rabin_karp("merhabatarif", "tarif"))

Kendini test et

hash hesabı

h = (h * base + ord(text[____)) % mod

Cevabı göster

h = (h * base + ord(text[i)) % mod

Hash çakışması bulunursa ne yapılır?
```
if h == pattern_hash:
    ...
```
- Eşleşme kabul edilir
- Arama durdurulur
- Karakter karakter doğrulanır
- Yeni mod seçilir
Cevabı göster

Karakter karakter doğrulanır — Hash çakışması karakter karakter doğrulamayla çözülür.
Rabin-Karp kavramları

yuvarlanan hash

O(1) kaydırma
mod

Büyük asal
çakışma

Doğrulama gerekli
base

256 karakter

Sıradaki ders: Boyer-Moore

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler