Vyhledávání Rabin-Karp

O(n + m) avg

Rabin-Karp promění hledání řetězce v porovnávání čísel. Vzor zahashuje jednou, pak hashuje každé okno textu délky m a porovnává čísla místo znaků. Trik je klouzavý hash: posun okna o krok odebere příspěvek odcházejícího znaku a přidá příchozí v konstantním čase, takže všechny hashe oken stojí dohromady O(n). Když se hash okna rovná hashi vzoru, stejně ověří znak po znaku — shodné hashe nezaručují shodné řetězce ("falešný zásah"), s dobrým modulem jsou ale vzácné. Průměrný čas je O(n + m); patologický text může vynutit O(n·m). Vyniká při hledání mnoha vzorů najednou. Tady se shodné okno ověřuje teal/oranžově a potvrzené shody zezelenají.

Text a vzor
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Zahashuj vzor a zahashuj první okno textu.
  2. Liší-li se hash okna od hashe vzoru, přeskoč ho a posuň se na další.
  3. Shodují-li se hashe, ověř okno znak po znaku.
  4. Posuň hash dopředu v O(1) a opakuj; potvrzené shody se zaznamenají.

Pseudokód

1rabinKarp(text, pattern):           # O(n + m) avg2  ph ← hash(pattern); th ← hash(text[0..m-1])3  for each window start s:4    if th = ph:                      # hashes agree5      verify text[s..s+m-1] = pattern char by char6      (equal hashes, unequal text = spurious hit)7    roll th to the next window in O(1)