StringsString Algorithms

Rabin–Karp

Compare a rolling hash of each text window with the pattern hash and verify only on hash hits.

Learn Rabin–Karp →
a
a
0
b
1
x
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
y
11
pattern
a
0
b
1
c
2
a
3
b
4
y
5
1/17Use a rolling hash with base 256 modulo 101. h = base^(m-1) mod q = 36 is the weight of the window's leading character.
Current text windowVerifying a hash hitMatchSpurious hit (hash equal, text differs)
PseudocodeLearn Rabin–Karp →
1h = base^(m-1) mod q
2hp = hash(pattern); ht = hash(text[0..m-1])
3for s in 0 .. n-m:
4  if hp == ht:
5    verify text[s..s+m-1] == pattern  # rule out spurious hit
6  if s < n-m:
7    ht = (base*(ht - text[s]*h) + text[s+m]) mod q
Variables
base256
q101
h36
Complexity
best O(n + m)
avg O(n + m)
worst O(n · m)
space O(1)
Speed