Visualizer CodeViz · Algorithms, visualized

Part II · Substring search · week 6

Rabin–Karp

Hash the pattern once, then hash every window of the text — each in constant time from the previous one. Fingerprints instead of characters.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

time~7n (Monte Carlo)
rolling hashO(1) per shift
false positive~1/q per window
extends to2-D, many patterns

Reference: Sedgewick & Wayne, §5.3; Karp–Rabin 1987.

Rabin–Karp in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def search(pat, txt, q=997, R=256):
    # Compare HASHES, not characters. The hash of the next window follows
    # from the current one in constant time: remove the leading character,
    # shift, add the trailing one. All arithmetic is mod q.
    m, n = len(pat), len(txt)
    pat_hash = 0
    for c in pat:
        pat_hash = (pat_hash * R + ord(c)) % q     # Horner's method
    rm = pow(R, m - 1, q)                          # R^(m-1) mod q
    txt_hash = 0
    for i in range(m):
        txt_hash = (txt_hash * R + ord(txt[i])) % q
    if txt_hash == pat_hash and txt[:m] == pat:
        return 0
    for i in range(m, n):
        txt_hash = (txt_hash + q - rm * ord(txt[i - m]) % q) % q  # remove
        txt_hash = (txt_hash * R + ord(txt[i])) % q               # add
        start = i - m + 1
        if txt_hash == pat_hash and txt[start:start + m] == pat:
            return start                           # verify, then accept
    return n

Why it works

The rolling hash

The window hash is a base-R number mod q. To advance one position: subtract the leading character times Rm−1, multiply by R, add the new trailing character. Constant work per shift, so the whole scan is linear regardless of the pattern length — the pattern's length only affects the setup. Note + q before the subtraction: it keeps the value non-negative, which matters in languages where % can return a negative result.

Monte Carlo and Las Vegas

Two hashes matching does not prove the strings match. Monte Carlo Rabin–Karp skips the verification and accepts a tiny error probability (~1/q per window, so choose q huge) in exchange for a guaranteed linear running time. Las Vegas — the version above — verifies each hit character by character, so it is always correct but has a quadratic worst case if a pathological input forces constant collisions. Neither is strictly better; the choice is between “probably right” and “probably fast”.

Horner's method

hash = hash * R + ord(c) evaluates the polynomial in one pass with no exponentiation, taking the modulus each step so nothing ever overflows. The same trick appears in string hashing for hash tables — that 31 * h + c loop is Horner's method with R = 31.

What it is good for

Rabin–Karp's real advantage is generality, not speed: it extends naturally to two-dimensional patterns (image matching), to searching for many patterns at once (hash them all into a set — the basis of plagiarism and duplicate detection), and to finding repeated substrings. When you need one pattern in one string, Boyer–Moore is usually faster.

What to try in the animation

The default is the course's example (π's digits, q = 997). Watch the window hash: it is recomputed in constant time, never from scratch.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Rabin–Karp in the player →

The rest of Substring search