How does the Rabin-Karp algorithm work?

Rabin-Karp hashes the pattern to a single number, then slides a window the size of the pattern across the text and hashes each window. It compares hashes, not characters: only when a window hash equals the pattern hash does it verify the characters to rule out a coincidence. The trick is a rolling hash that updates in O(1) per shift instead of re-hashing the whole window.

What is a rolling hash?

A rolling hash treats a window of characters as a number in some base and updates it in constant time when the window slides by one: subtract the contribution of the character leaving the front, multiply by the base, and add the character entering the back. This avoids recomputing the hash of the whole window from scratch, which would cost O(m) each step.

Why does Rabin-Karp still verify characters after a hash match?

Because different strings can hash to the same number, a collision. A hash match is only a strong hint, not a proof, so the algorithm confirms with a direct character comparison. With a good hash and modulus, collisions are rare, so verification runs seldom and the average cost stays low.

What is Rabin-Karp used for?

Its average time is O(n + m), and it shines when searching for many patterns at once (hash them all and check each window hash against a set) and in fingerprinting tasks: plagiarism detection, near-duplicate document detection, and file deduplication with content-defined chunking, where comparing short fingerprints is far cheaper than comparing full content.

Algorithm · Strings & Text

The Rolling Hash.

Don't memorize Rabin-Karp — watch the hash roll. Instead of comparing characters at every position, turn each window of text into a single number and compare numbers. As the window slides, the hash updates in O(1) — drop the leaving character, add the entering one. Only when a window number equals the pattern number do you bother checking the characters.

rolling hash · fingerprint · verify · O(n + m) avg

FINGERPRINT

Hash the pattern once into a single number to compare against.

ROLLING HASH

Slide the window and update the hash in O(1), not O(m).

HASH MATCH

Equal hashes are a strong hint — but not a proof.

VERIFY

On a hash match, confirm the characters to rule out a collision.

rabin-karp.sim — find "ABC" in "ABABCABAB"

Ready

Searching for ABC (hash 28) in the text. Press Step to slide the window; each shift rolls the hash in O(1). When the window hash equals 28, verify the characters.

pattern "ABC" → hash 28

—

Window hash

Char checks

Compare numbers, not letters

The naive search lines the pattern up at every position and compares character by character — O(n·m) in the worst case. Rabin-Karp replaces most of those character comparisons with a single number comparison. It reads the window as a base-b number modulo a prime, so two equal windows always have equal hashes. The magic is the rolling update: sliding one step to the right does not require re-reading the window, just a subtract, a multiply, and an add.

Hash the pattern and first window

Compute one number for the pattern and one for the opening window, each O(m), once.

Compare hashes

If the window hash equals the pattern hash, it is a candidate; otherwise skip it entirely — no characters touched.

Roll forward

Slide by one: subtract the leaving character times bᵐ⁻¹, multiply by b, add the entering character — O(1).

Verify on a match

A hash match could be a collision, so confirm with a direct character check before declaring a real match.

Average time

O(n + m)

Worst case

O(n·m)

Roll per shift

O(1)

Space

O(1)

The worst case (many collisions or an adversarial input) degrades to naive speed, so for a single pattern KMP is the safer linear-time choice. Rabin-Karp wins when you search for many patterns at once — hash them all into a set and test each window hash against it — and in fingerprinting: plagiarism detection, near-duplicate finding, and content-defined chunking for deduplication all lean on rolling hashes.

Check yourself

1 · What does Rabin-Karp compare at each window?

It compares hashes first; only a hash match triggers a character-level verification.

2 · Why is the rolling hash update O(1)?

Subtract the leaving char contribution, shift the base, add the new char — constant work per slide, no re-scan.

3 · Why verify characters after a hash match?

A hash match is a strong hint, not a proof; verification rules out coincidental collisions.

Questions

Rabin-Karp vs KMP?

KMP guarantees O(n + m) for a single pattern by never re-reading text, using a precomputed failure table. Rabin-Karp is O(n + m) on average but can degrade with collisions; its edge is multi-pattern search and fingerprinting, where hashing many things and comparing numbers is cheaper.

Why use a prime modulus?

Taking the hash modulo a prime keeps the numbers small (they would otherwise overflow) and spreads hash values more uniformly, reducing collisions. Some implementations use two independent moduli to make collisions astronomically unlikely.

How does deduplication use rolling hashes?

Content-defined chunking rolls a hash over a file and cuts a new chunk whenever the hash hits a pattern of low bits. Identical regions across files produce identical chunk fingerprints, so storage systems store each unique chunk once.

Roll the fingerprint, verify on a hit.

Numbers beat letters when they can. Hash, roll in O(1), confirm on a match.

← All algorithms KMP → Hash Table → Big-O Cheatsheet →

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

The Rolling Hash.

Compare numbers, not letters

Hash the pattern and first window

Compare hashes

Roll forward

Verify on a match

Check yourself

Questions

Roll the fingerprint, verify on a hit.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Compare numbers, not letters

Hash the pattern and first window

Compare hashes

Roll forward

Verify on a match

Check yourself

Questions

Roll the fingerprint, verify on a hit.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.