Rolling Hash & Rabin–Karp

Comparing two strings costs O(m); comparing two numbers costs O(1). Rolling hashes turn every window of a text into a number you can update in constant time, which powers plagiarism checkers and duplicate file finders.

intermediate⏱ 12 min read

←Builds on

1Hash Tables: Sets & MapsA rolling hash is a hash function that updates in O(1) as the window slides.11Naive Pattern MatchingRabin–Karp keeps the sliding window but compares fingerprints before characters.9Fast Exponentiation & Modular ArithmeticA polynomial hash is computed modulo a large prime, with the powers of the base taken mod p.

Leads to→

+Manacher's AlgorithmHashing a string and its reverse tests any palindrome in O(1), and binary search on top finds every radius in O(n log n); Manacher drops the hash and the log factor.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01A string as a number

You met hash functions in the hash table lesson: turn a key into a number, then use the number. For strings the standard choice is the polynomial hash. Read the string as digits of a number in base p:

h(s) = s[0]·p^(m−1) + s[1]·p^(m−2) + … + s[m−1] (mod M)

With A=1, B=2, p = 31 and M = 97, the string ABAB becomes 27. Equal strings always get equal hashes. Different strings usually get different hashes.

You compute it left to right with h = h·p + code(c), taking mod M at each step so the numbers stay small.

02Rolling the window in O(1)

Rabin–Karp hashes the pattern once, then slides a window of length m over the text. Recomputing each window from scratch would cost O(m) again. The trick is that neighbouring windows share m − 1 characters:

remove the leading character: subtract code(first)·p^(m−1)
shift everything one place: multiply by p
add the new character: add code(next)

That is three arithmetic operations per step, whatever the length of m. Precompute p^(m−1) mod M once. Watch out for negative numbers after the subtraction: add M before taking the remainder.

03Collisions: always verify

A hash squeezes many possible strings into M values, so two different strings will sometimes share a hash. That is a collision. With M = 97, AA and DE both hash to 32.

So when a window's hash equals the pattern's hash, Rabin–Karp compares the actual characters before reporting a match. A false alarm costs O(m) but never gives a wrong answer.

In real code use a large prime like M = 10⁹ + 7 with a random base p, or two different moduli at once. Collisions then become so rare that the expected running time is O(n + m). The same rolling idea also answers "are these two substrings equal?" in O(1) after O(n) preprocessing of prefix hashes.

Cost at a glance

Hash the patternO(m)

Roll one windowO(1)

Rabin–Karp, expectedO(n + m)

Substring equality after prefix hashesO(1)

Remember

A polynomial hash reads the string as a base-p number modulo M, so equal strings get equal fingerprints.
Rolling the window (remove first, multiply, add next) updates the hash in O(1) per shift.
Equal hashes only suggest a match: verify the characters, and use a large modulus to keep collisions rare.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Compare the two numbers in the header: characters are only checked when the window hash equals the pattern hash.

Interactive visualizerfocus here, then space ← →

Rabin–Karp (rolling hash) · pattern hash: 27

ABABCABAB

Build the pattern hash char by char: fold in 'A' → 1 (mod 97).

Pseudocode

 1 patHash = Σ code(pat[i]) · p^(k-1-i)  mod m 2 windowHash = hash of text[0..k-1] 3 if windowHash == patHash: verify chars (guard against collisions) 4 else: not a match here 5 roll to next window in O(1): drop leading char, shift, add next

1 / 1

Check

Three questions. Pick an answer to see why.

With A=1, B=2, p = 10 and no modulus, what is the hash of "BAB"?

The window hash equals the pattern hash. What should Rabin–Karp do?

Why is rolling to the next window O(1) and not O(m)?

Practice

Real problems to lock it in, easiest first.

LeetCodeRepeated DNA Sequences intermediate↗CSESString Matching intermediate↗LeetCodeDistinct Echo Substrings advanced↗LeetCodeLongest Duplicate Substring advanced↗