rabin karp algoritması

• belirtilen hash fonksiyonu (rolling hash) tarafından hesaplanan sonuca bir önceki elemanı çıkarıp bir sonraki elemanı ekleme ile sıradaki hash'i hesaplayabilmemiz işlemine dayanır.
  
  örneğin string için s diyelim, hash fonksiyonumuz da aşağıdaki 3. derece polinom olsun
  
  p(x) = s[0] + s[1] * x + s[2] * x^2 + s[3] * x^3
  
  genellersek:
  
  k polinomun derecesi
  
  pi(x) = s[i] * x ^ (k - 3) + s[i+1] * x ^ (k-2) + s[i+2] * x ^ (k-1) + s[i+3] * x ^ k
  
  bir sonraki hash'i bulmak icin bir önceki hash değerini kullanabiliriz
  
  pi+1(x) = (pi(x) - s[i]) / x + s[i + k] * x ^ k
  
  aradığımız substring'in hash'ini bir köşeye koyup, yukarıdaki özelliğin yardımıyla text içerisinde adım adım substring hash'lerini hesaplamaya başlarsak hızlı bir şekilde eşleşme yakalayabiliriz.