Rabin-Karp — Rolling-Hash String Matching

Slide a length-m window over the text, roll the hash in O(1) (remove the leading char, add the trailing char), compare to the pattern hash, and verify on a hit.

step 0

Text tape (window highlighted)

current window leaving char entering char hash hit (candidate) verified match

Pattern & hashes

hash(pattern)-
hash(window)-
equal?-

Rolling update (O(1))

Press Step to begin.
Press Step to begin. We hash the pattern once, hash the first window, then roll across the text. Each hit is verified character by character.
Self-contained visualization. Uses base = 256 and a small prime modulus for readable hash values (real implementations use a large prime near 109 or 261−1). The verify step compares characters on every hash hit, so collisions never produce a false reported match. See junior.md and professional.md for the rolling-update derivation and the collision-probability bound.