Rabin-Karp — rolling hash, O(n+m) expected: Question bank

Before we start, one word we lean on: a collision is when two different strings produce the same hash number. It is the villain of every question here.

True or false — justify

Two strings with equal hashes are guaranteed to be the same string

False. Equal hash is necessary but not sufficient — two different strings can collide, so you must still verify character-by-character.

Two strings with different hashes are guaranteed to be different strings

True. A correct hash is a function: identical inputs always give identical outputs, so unequal outputs force unequal inputs. This is why a hash mismatch lets us skip instantly.

Rabin-Karp is

O (n + m)

in the worst case

False. It is

O (n + m)

expected; the worst case is

O (nm)

when nearly every window collides and we verify everywhere (e.g. a tiny prime or adversarial input).

Choosing a larger prime

q

can never hurt correctness

True for correctness — it only lowers collision probability (~

1/ q

). It can hurt if

q

is so large that

b \cdot q

overflows your integer type, so keep

q

within a safe range (see Modular Arithmetic).

The rolling update lets us skip recomputing the whole hash each slide

True. Dropping the leading term, multiplying by

b

, and adding the new term is

O (1)

, versus

O (m)

to rebuild — that single fact is the entire speedup.

Rabin-Karp can miss a genuine occurrence of the pattern

False. Equal strings always produce equal hashes, so a real match never fails the hash test. We only risk extra work (false positives), never missed matches.

Using

b

smaller than the alphabet size is fine

False (dangerous). If

b

is smaller than the number of distinct symbols, different digit strings map to the same base-

b

number even before taking mod, inflating collisions. Pick

b \geq

alphabet size.

With double hashing (two independent hashes), you can safely skip verification

Mostly-safe but not proof. Collision probability drops to about

1/ q_{1} q_{2}

, tiny enough for contests, but it is still a probability, not a guarantee. For an adversary-proof or provably-correct match, verify.

Spot the error

A student writes H = (H - T[i]*Phigh) * b + T[i+m] and skips % q. What breaks?

The number grows past

b^{m}

, overflowing the integer type and giving garbage; the whole point of

mod q

is to keep values bounded. Every step must reduce mod

q

A student computes (H - T[i]*Phigh) % q and gets a negative number, then uses it directly. Error?

In most languages % on a negative operand yields a negative result, which then never equals the pattern's hash (always in

[0, q)

), causing missed matches. Fix: ((x) % q + q) % q.

A student recomputes Phigh = pow(b, m-1) % q inside the sliding loop. Error?

b^{m - 1} mod q

is a constant for the whole search, so recomputing it each iteration makes every step

O (lo g m)

(or worse) and destroys the

O (1)

roll. Precompute it once.

A student picks

q = 13

"to keep arithmetic easy." Error?

A tiny prime causes collisions on almost every window, so verification runs everywhere and the algorithm degrades to

O (nm)

. Use a large prime like

1 0^{9} + 7

A student maps 'a' -> 0 and hashes the whole alphabet from 0. Any subtle bug?

Mapping a character to

0

means leading 'a's contribute nothing, so "a", "aa", "aaa" can share hash

0

. Map characters to

1.. k

(or add 1) so length is encoded.

A student reports a match as soon as h(P) == H_i, never comparing letters. Error?

That treats the hash as a proof when it is only a filter — a collision would report a fake match. Always run the

O (m)

character check on a hash hit.

A student uses H_{i+1} = (H_i * b - T[i]*b^m + T[i+m]) % q. Is this wrong?

Not wrong — it is an algebraically equal rearrangement (distribute the

\times b

first), but it needs

b^{m}

precomputed instead of

b^{m - 1}

, and still needs the add-

q

trick. Both forms are fine if consistent.

Why questions

Why multiply by

b

(not add) when rolling the window?

Every remaining character must shift one place higher in the base-

b

number after we drop the leading digit — multiplying by

b

raises every exponent by one at once, exactly like appending a digit shifts a decimal number left.

Why subtract

T [i] \cdot b^{m - 1}

specifically, not

T [i]

alone?

The leading character sits in the highest place value

b^{m - 1}

, so its contribution to the number is

T [i] \cdot b^{m - 1}

, not

T [i]

. Removing only

T [i]

would leave most of it behind.

Why a prime

q

rather than any large number?

A prime spreads hash values more uniformly and avoids common factors between

b

and

q

that would collapse many strings to the same residue — see Modular Arithmetic for why shared factors cause clustering.

Why is the collision probability roughly

1/ q

, and what does that recall?

With a uniform hash into

q

buckets, a random other string lands on the pattern's value with chance

\approx 1/ q

. This is the Birthday Paradox intuition: collisions become likely once you hash about

q

strings.

Why does Rabin-Karp shine at multi-pattern search?

You can hash many patterns into a set once, then check each window's single hash against the set in

O (1)

— one text pass finds all of them, unlike Knuth-Morris-Pratt which is built around one pattern.

Why prefer Knuth-Morris-Pratt or Z-Algorithm when worst case matters?

They give guaranteed

O (n + m)

with no collision risk, whereas Rabin-Karp's guarantee is only expected — adversarial input can force

O (nm)

Why does the same rolling idea power

O (1)

substring comparison?

Precomputing prefix hashes lets you extract any substring's hash in

O (1)

, so equality of arbitrary ranges becomes a number comparison — see String Hashing for Substring Comparison.

The hash is a fast filter, never a proof: verify on hits, keep values non-negative and reduced mod a large prime, precompute $b^{m - 1}$ once, and remember the guarantee is expected, not worst-case.

Connections

Parent: Rabin-Karp — the derivation these traps guard
Hashing — where collisions come from
Modular Arithmetic — negatives, primes, and $g cd (b, q)$
Birthday Paradox — why $\sim 1/ q$ collision chance
Knuth-Morris-Pratt · Z-Algorithm — guaranteed linear alternatives
String Hashing for Substring Comparison — same rolling idea, range queries

Question bank — Rabin-Karp — rolling hash, O(n+m) expected