Problem Statement

Rabin-Karp String Matching

We want to find where a small word (the pattern) shows up inside a bigger piece of text. The slow way is to line the pattern up at every spot and check letter by letter. Rabin-Karp speeds this up with a rolling hash. A hash is just a number that stands in for a string, like a fingerprint. If two strings have different fingerprints, they cannot be the same string. So we turn the pattern into one number, then slide a window of the same length across the text and turn each window into a number too. A "window" is a chunk of the text the same length as the pattern, the part we are currently looking at. Comparing two numbers is fast, so we only do the slow letter-by-letter check when the fingerprints actually match. The "rolling" part means that when the window moves over by one character, we update the number quickly instead of rebuilding it from scratch.

mediumStringHash TableStringsTime: O(n + m) · Space: O(1)

Signals to notice

pattern matching via rolling hashO(1) window hash updateverify on match

Brute force first

Compare every window — O(nm).

The key insight

Rolling hash: update hash in O(1) per slide. Compare characters only on hash match. Average O(n+m).

Trace it on `text="aaaa", pattern="aa" (ord('a')=97)`

init: n=4, m=2, BASE=256, MOD=1e9+7, h=256^1=256
pHash=hash("aa")=97*256+97=24929; tHash=hash(text[0:2]="aa")=24929
i=0: pHash==tHash and text[0:2]="aa"==pattern -> record 0; roll: tHash=((24929-97*256)*256+97)%MOD=24929
i=1: pHash==tHash and text[1:3]="aa"==pattern -> record 1; roll: tHash=((24929-97*256)*256+97)%MOD=24929
i=2: pHash==tHash and text[2:4]="aa"==pattern -> record 2; i==n-m so no roll
loop ends (i ranges 0..2); return [0, 1, 2]

What must stay true

Rolling hash detects potential matches in O(1). Character comparison verifies (handles collisions).

Shape of the loop

h = BASE^(m-1)                      # mod MOD
pHash = hash(pattern)               # sum ord*BASE^k, mod MOD
tHash = hash(text[0..m-1])
for i in 0..n-m:
    if pHash == tHash and text[i..i+m-1] == pattern:   # half-open window of length m
        record i
    if i < n-m:
        tHash = ((tHash - ord(text[i])*h)*BASE + ord(text[i+m])) % MOD

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not verifying hash matches — collisions give false positives.

Strings Pattern