Rabin-Karp compares hashes before comparing strings. For a pattern of length 10^6 in a text of length 10^7 with a polynomial hash modulo a prime near 2^61, bound the probability of any false match, and describe the input that breaks a hash taken modulo 2^64 with a fixed base.

Rabin-Karp compares hashes before comparing strings. For a pattern of length 10^6 in a text of length 10^7 with a polynomial hash modulo a prime near 2^61, bound the probability of any false match, and describe the input that breaks a hash taken modulo 2^64 with a fixed base.

Approach: Treat the hash as a polynomial evaluated at a random point and count its roots, then think about what an adversary can construct when the modulus is a power of two and the base is public.

About 4 * 10^{-6}, and a Thue-Morse style anti-hash input breaks the power of two modulus. Two distinct strings of length m collide exactly when the difference polynomial of degree m - 1 vanishes at the chosen base, and a non-zero polynomial has at most m - 1 roots modulo a prime p, so a uniformly random base gives a false match probability of at most (m-1)/p per alignment, which is 10^6 divided by 2^61, that is 4.3 * 10^{-13}. Over the roughly 10^7 alignments a union bound gives about 4 * 10^{-6} for any false match anywhere, so verifying a hash hit with a full comparison is optional at that scale. The rolling update is O(1) per shift, giving O(n + m) expected. Modulo 2^64 the argument collapses, because the ring has zero divisors and the base is public: the Thue-Morse sequence produces pairs of strings of length 2^k that collide under every odd base modulo 2^64, so an adversary submitting such an input forces a full comparison at every alignment and drives the running time to Theta(nm). Choosing the base at random at run time from a large prime field removes the attack.

Follow-up: How do you make a rolling hash that supports substring equality tests for arbitrary ranges in O(1) after linear preprocessing?

Key concepts: polynomial hash, false match, random base, anti-hash input.