Visualize

Pattern visualizer

Rabin Karp Algorithm

Comparing a pattern against every window of the text re-reads the same characters over and over. Rabin-Karp replaces each window with one number and compares numbers instead, then repairs the number as the window slides: the leaving character is subtracted out and the entering one shifted in, so a new window costs a constant amount of work rather than a fresh pass over the pattern. The catch is that a hash squeezes every possible window into a limited range of remainders, so two different strings can land on the same number. This trace uses a deliberately small modulus to make that happen twice: three windows hash equal, and only one of them really is the pattern. The character comparison after a hash hit is what separates them, which is why it belongs in the algorithm and not in a comment. Animated on: text = "abracadabra", pattern = "cad" — report every index where the pattern starts. Base 26, modulus 79, chosen so a collision actually happens..

A rolling hash, and the check you cannot skip

time O(n + m) expected, O(n * m) worst casespace O(1)step 1 / 15
a
[0]
b
[1]
r
[2]
a
[3]
c
[4]
a
[5]
d
[6]
a
[7]
b
[8]
r
[9]
a
[10]
line 1

Looking for "cad" inside "abracadabra". Comparing the pattern against all 9 windows character by character costs up to 27 comparisons. Instead each window gets ONE number — a hash — and numbers compare in a single operation.

Pseudocode
1FUNCTION rabinKarp(text, pat)
2  m <- LENGTH(pat)
3  high <- POWER(d, m - 1) MOD q
4  hp <- HASH(pat)
5  hw <- HASH(text[0 .. m - 1])
6  FOR i <- 0 TO LENGTH(text) - m
7    IF hw = hp
8      IF text[i .. i + m - 1] = pat
9        APPEND i TO out
10    IF i < LENGTH(text) - m
11      hw <- ((hw - VAL(text[i]) * high) * d + VAL(text[i + m])) MOD q
12  RETURN out

← / → step · space play · Home restart

Where to practice Strings

Practice Strings problemsAll Strings problemsBack to roadmap