Rabin-Karp string matching

O(n + m) avg

Rabin-Karp turns string search into number comparison. It hashes the pattern once, then hashes each length-m window of the text and compares numbers instead of characters. The trick is the rolling hash: sliding the window one step removes the leaving character's contribution and adds the entering one in constant time, so all the window hashes cost O(n) together. When a window's hash equals the pattern's, it still verifies character by character — equal hashes don't guarantee equal strings (a "spurious hit"), though with a good modulus they're rare. Average time is O(n + m); a pathological text can force O(n·m). It shines when searching for many patterns at once. Here the matched window is verified in teal/orange and confirmed matches turn green.

Text & pattern
Edit the input and press Play

How it works

  1. Hash the pattern, and hash the first window of the text.
  2. If the window's hash differs from the pattern's, skip it and roll to the next.
  3. If the hashes match, verify the window character by character.
  4. Roll the hash forward in O(1) and repeat; confirmed matches are recorded.

Pseudocode

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)