Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 225 ยท Strings

Rabin-Karp and String Hashing

Learn the Rabin-Karp algorithm and polynomial rolling hashes in Python. Search for patterns, handle collisions, match many patterns and compare substrings fast.

KMP searches by being clever about characters. Rabin-Karp searches by being clever about numbers. It turns every window of the text into a single integer, called a hash, and compares that integer with the hash of the pattern. Comparing two integers takes one step, no matter how long the pattern is.

The trick that makes this fast is the rolling hash: when the window slides one character to the right, the new hash is computed from the old one in O(1) instead of re-reading all m characters. This gives an expected running time of O(n + m). The same idea powers plagiarism detectors, file-sync tools such as rsync, and "find all duplicate substrings" problems.

In this lesson you will build the hash step by step, handle collisions honestly, search for many patterns at once, and use a prefix-hash table to compare any two substrings in O(1). If hashing is new to you, Hash Functions goes deeper into what makes a good one.

The idea: compare fingerprints, not strings

Suppose text has length n and pattern has length m. The naive method compares up to m characters at each of the n - m + 1 alignments. Rabin-Karp instead does this:

  1. Compute hash(pattern) once.
  2. Compute the hash of every length-m window of the text.
  3. Only when a window's hash equals the pattern's hash, compare the actual characters to be sure.

If the hash function were free and perfect, step 3 would never be needed. Real hashes can collide: two different strings can produce the same number. That is why a hash match is only a candidate, and a character-by-character check confirms it.

TEXT
text:     c a b a c a b
pattern:  a c a                hash(pattern) = H

window 0: c a b   hash != H    skip
window 1: a b a   hash != H    skip
window 2: b a c   hash != H    skip
window 3: a c a   hash == H    verify characters -> real match at 3
window 4: c a b   hash != H    skip

A polynomial hash

Treat the string as a number written in some base B. With B = 10 and digits, "472" is 4*100 + 7*10 + 2. For letters we use their character codes (ord) and a base such as 256 (one slot per possible byte value) or any base bigger than the alphabet:

TEXT
hash("abc") = ord('a')*B^2 + ord('b')*B^1 + ord('c')*B^0

Numbers like this explode, so we keep only the remainder modulo a big prime M. Python integers never overflow, but they get slow when they grow, so we still reduce at every step.

Python A polynomial hash by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop is Horner's rule: multiply the running value by B, then add the next character. It computes the polynomial in one pass.

The rolling step

Let the current window be s[i .. i+m-1] with hash h. The next window drops s[i] and adds s[i+m].

  • The oldest character has weight B^(m-1), so remove it: h - ord(s[i]) * B^(m-1).
  • Everything that is left moves one place to the left, which means multiplying by B.
  • Add the new character: + ord(s[i+m]).
TEXT
window "abc"  ->  window "bcd"

h("abc") = a*B^2 + b*B + c
remove a:      b*B + c
shift (xB):    b*B^2 + c*B
add d:         b*B^2 + c*B + d  = h("bcd")

We precompute high = B^(m-1) mod M once. In Python, pow(BASE, m - 1, MOD) does fast modular exponentiation. A negative intermediate value is fine in Python because % always returns a non-negative result for a positive modulus (in C, Java or C++ you would add M first).

Python Rolling hash equals recomputing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row prints True: the O(1) update agrees with hashing the window from scratch (which costs O(m)).

Putting it together:

Python Rabin-Karp search with counters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the last line: when nothing matches there are no candidates at all, so the search never compares a single character. On "aaaaaaaaaa" every window matches, so the verification cost is m per match, as it must be when the output itself has that many positions.

Collisions and the choice of modulus

A hash maps a huge set of strings onto only M values, so by the pigeonhole principle collisions exist. What matters is how likely they are.

  • With a random-like hash and modulus M, a window collides with the pattern with probability about 1/M. Over n windows the expected number of false candidates is about n/M. With M around 10^9 and a text of a million characters, that is roughly one in a thousand.
  • Each false candidate costs O(m) to rule out, so the expected total is O(n + m) plus a tiny correction.
  • The worst case is O(n*m): if many windows collide (an unlucky modulus or an attacker choosing the input), you verify nearly every window. Fixed, well-known parameters are guessable. Production code picks the base at random when the program starts.

Never skip the verification step in a search where a wrong answer matters. A hash-only comparison is a probabilistic answer: fast, but occasionally wrong. Verification turns it into a Las Vegas algorithm (always right, usually fast). Skipping it gives a Monte Carlo algorithm (always fast, rarely wrong). Both have uses, but you should choose on purpose.

To see collisions with your own eyes, use a tiny modulus:

Python Collisions with a tiny modulus

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The matches are identical for every modulus because we verify; only the number of false alarms changes. With a good modulus it drops to zero.

Searching for many patterns at once

Rabin-Karp shines when all patterns have the same length m. Store the pattern hashes in a dictionary from hash to the patterns that produce it, then run one rolling pass over the text. Each window needs one dictionary lookup, so the whole job is O(n + k*m) for k patterns, instead of running a search k times.

Python Many patterns in one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For patterns of different lengths, group them by length and run one pass per distinct length, or use a trie based method.

Hashing substrings for equality: prefix hashes

A rolling hash only sees one window at a time. If you must compare arbitrary substrings, precompute prefix hashes, just as prefix sums answer range-sum queries:

  • pre[i] is the hash of s[:i], built by pre[i+1] = pre[i]*B + ord(s[i]).
  • pw[i] is B^i mod M.
  • The hash of s[l:r] is (pre[r] - pre[l] * pw[r-l]) mod M.

Building both tables is O(n); then any substring hash is O(1). Two substrings are (almost certainly) equal when their hashes are equal.

Python O(1) substring comparison

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last function combines the hash with binary search on the answer: if a repeated substring of length L exists, one of length L - 1 does too, so the answer is monotonic. Each check is O(n), and there are O(log n) checks. This approach uses a 61-bit modulus so accidental collisions are extremely unlikely. A suffix array solves the same problem with no probability involved.

Complexity

Time Extra space
Naive search O(n*m) worst O(1)
Rabin-Karp (expected) O(n + m) O(1)
Rabin-Karp (worst case, many collisions) O(n*m) O(1)
Prefix hashes: build / query O(n) / O(1) O(n)

Common mistakes

  • Forgetting to verify a hash match, which makes the search silently wrong on collisions.
  • Weak parameters. A tiny modulus or a base of 1 gives many collisions. Use a large prime modulus and a base larger than the alphabet (or random).
  • Mapping characters to 0. If 'a' maps to 0, then "a" and "aa" hash the same. Use ord() or ord(c) - 96, never a zero value.
  • Off-by-one in the rolling update, such as using B^m instead of B^(m-1) for the dropped character.
  • Comparing hashes of different lengths in prefix-hash code without adjusting for length.

When to use it

Reach for Rabin-Karp when you need many patterns of the same length, when you want to detect duplicate substrings or near-duplicate documents, or when you need O(1) substring equality. For one plain pattern search, KMP or the Z-algorithm have a guaranteed O(n + m) bound, and Python's built-in in and find are faster than any pure-Python version here.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does Rabin-Karp still compare characters after a hash match?

    Many strings map onto few hash values, so equal hashes only make a window a candidate. Verification makes the result always correct.
  2. 2. In the rolling update, which weight does the character that leaves the window have (window length m, base B)?

    The oldest character is the leftmost digit of the polynomial, whose weight is B^(m-1). It is removed before the remaining hash is multiplied by B.
  3. 3. What is the worst-case running time of Rabin-Karp with verification?

    If almost every window collides with the pattern hash, each one costs O(m) to verify, giving O(n*m). With good parameters this is very unlikely.
  4. 4. When does searching many patterns with one Rabin-Karp pass work best?

    A window of fixed length m has one hash, which you look up in a dictionary of pattern hashes. Different lengths need one pass per length.
  5. 5. How do prefix hashes let you compare two substrings in O(1)?

    After an O(n) precomputation of prefix hashes and powers of the base, any substring hash is one subtraction and one multiplication.

Summary

  • Rabin-Karp compares hashes of text windows with the pattern hash, then verifies real matches.
  • A polynomial hash treats characters as digits in base B, reduced modulo a large prime.
  • The rolling update h = (h - old*B^(m-1)) * B + new costs O(1), so all windows cost O(n) in total.
  • Expected time is O(n + m); the worst case is O(n*m) when collisions pile up. Verification keeps answers correct.
  • It handles many equal-length patterns in one pass and, with prefix hashes, gives O(1) substring equality.
  • Choose large moduli (or random bases) and never map a character to 0.

Next: The Z-Algorithm, which finds all matches in guaranteed linear time using an array of prefix matches.