rabin karp algoritması

• bir yazı eşleştirme (string matching) algoritmasıdır.
  dijital dökümanlarda intihal tespitinde kullanılmaktadır.
  özel bir hash fonksiyonu kullanarak çok efektif sonuçlar alınmaktadır.
  
  örneğin elimizde bir tane pattern olsun cheribum
  bu pattern'i çok uzun bir dökümanda aramak istiyoruz "...cheradsafdagcherasdsafdgcheribumsadfadgfs...."
  
  pattern'deki harfleri dökümanda tek tek karşılaştırmaktansa (şu şekilde)
  "cheribum" != "cheradsa" (eşit değil, bir karakter sağa kaydır)
  "cheribum" != "heradsaf" (eşit değil, bir karakter sağa kaydır)
  "cheribum" != "eradsafd" (eşit değil, bir karakter sağa kaydır)
  ...
  
  patterni ve dökümandaki karakterleri bir hash fonksiyonuna sokar ve bu fonksiyon değerlerini karşılaştırır (şu şekilde)
  
  hash(cheribum) = 37 (değerleri sallıyorum)
  hash(cheradsa) = 45 ( 37'ye eşit değil, bir karakter sağa kaydır, tekrar hash hesapla)
  hash(heradsaf) = 43 ( 37'ye eşit değil, bir karakter sağa kaydır, tekrar hash hesapla)
  ...
  hash(cheribum) = 37 (hash değerleri eşit, kelimeleri kontrol et)
  "cheribum" == "cheribum" (bulduk )
  
  şimdi hash olayının güzelliği nedir?
  verdiğim örnekte "cheribum" 8 karakterli oldukça kısa bir pattern. eğer bu pattern 1.000 karakterden oluşsaydı ve 10 milyon karakterlik bir dökümanda arama yapacak olsaydık, karakterleri teker teker eşleştirmek çok masraflı bir iş olacaktı.
  örneğin: 999 karakter eşleşiyor ancak son karakter farklı (o kadar emek boşa gitti, 1.000 karakter eşleşinceye kadar devam).
  
  hash fonksiyonunda ise:
  [1:1000] (ilk 1.000 karakter)
  [2:1001] (sağa kaydır, sonraki 1.000 karakter) olsun.
  kaydırma işlemini tek hamlede yapabiliyoruz, cünkü ortadaki 998 karakter aynı (1.000 tane karakteri tek tek karşılaştırmaya gerek kalmadı).
  
  esen kalın.
  
  --- spoiler ---
  
  hash = (karakterin ascii değeri) *( asal sayı) ^ (karakterin bulunduğu indis)
  
  örnek:
  ascii değerleri; a = 97, b = 98, r = 114.
  hash("abr") = (97 × 101^2) + (98 × 101^1) + (114 × 101^0) = 999,509
  
  --- spoiler ---