Algoritmul Rabin-Karp este un algoritm de potrivire / căutare a șirurilor dezvoltat de Michael O. Rabin și Richard M. Karp. Folosește hashing tehnică și forta bruta pentru comparație și este un bun candidat pentru detectarea plagiatului.

Termeni importanți

  • model este șirul care trebuie căutat. Luați în considerare lungimea modelului ca M personaje.
  • text este întregul text din care trebuie căutat modelul. Luați în considerare lungimea textului ca N personaje.

Ce este comparația forței brute?

În comparația forței brute, fiecare caracter al modelului este comparat cu fiecare caracter al textului până când sunt găsite caractere care nu se potrivesc.

Cum funcționează algoritmul Rabin-Karp

  1. Calculați valoarea hash de model
  2. Calculați valoarea hash a primei M personaje ale text
  3. Comparați ambele valori hash
  4. Dacă sunt inegale, calculați valoarea hash pentru următoarea M personaje ale text și compară din nou.
  5. Dacă sunt egali, efectuați o comparație a forței brute.
hash_p = hash value of pattern
hash_t = hash value of first M letters in body of text
do
	if (hash_p == hash_t) 
		brute force comparison of pattern and selected section of text
	hash_t= hash value of next section of text, one character over
while (end of text or brute force comparison == true)

Avantaj asupra algoritmului de potrivire a șirurilor naive

Această tehnică are ca rezultat o singură comparație per subsecvență de text și forța brută este necesară numai atunci când valorile hash se potrivesc.