StringsAlgorithmaka rolling hash matching, fingerprint matching

Rabin–Karp

Compare a rolling hash of each text window with the pattern hash and verify only on hash hits.

▶ VisualizePattern: Sliding WindowPractice (2)
Progress

Overview

Rabin–Karp treats strings as numbers. The pattern p is hashed once, and every length-m window of the text is hashed too. Because the hash is a polynomial in a base B modulo M, the hash of the next window can be derived from the current one in O(1) — a rolling hash — so all n - m + 1 window hashes cost O(n) total.

A hash equality is only evidence, not proof: two different strings may collide, called a spurious hit. Whenever hashes match, the algorithm compares the actual characters. With a large random modulus the expected number of spurious hits is tiny, giving expected O(n + m); the worst case degrades to O(nm) if an adversary engineers collisions.

pattern matchingrolling hashexpected O(n + m)multiple patternsspurious hits

Intuition

A mental model before the formal terms.

Think of a window of m digits sliding along a long decimal number. The value under the window is d₁d₂…dₘ. To slide one place right you do not re-read all m digits: subtract d₁ · 10^(m-1), multiply by 10, and add the new last digit. Rabin–Karp does exactly this with characters as digits in base B, and keeps the numbers small by working modulo M.

The modulus is what makes collisions possible: two different m-digit numbers can leave the same remainder. So a hash match is a "probably" that must be confirmed by reading the window for real.

How it works

  1. Choose a base B larger than the alphabet (e.g. 256) and a large prime modulus M (e.g. 10^9 + 7). Precompute high = B^(m-1) mod M.
  2. Compute hp = hash(p) and ht = hash(t[0..m-1]) where hash(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + … + s[m-1]) mod M.
  3. For each window start i: if ht == hp, compare t[i..i+m-1] with p character by character and report a match if they are equal (a hash hit that fails this check is a spurious hit).
  4. Roll to the next window: ht = ((ht - t[i]·high) · B + t[i+m]) mod M. Add M before taking the modulus in languages where % of a negative number is negative.

Why it works

Equal strings always produce equal hashes, so no genuine occurrence is ever skipped. The explicit verification on a hit means no false occurrence is ever reported. Correctness therefore does not depend on the hash quality at all — only running time does.

The rolling update is algebra: hash(t[i+1..i+m]) = (hash(t[i..i+m-1]) - t[i]·B^(m-1)) · B + t[i+m], and since addition, subtraction and multiplication commute with mod M, the same identity holds for the reduced values.

For a random prime M around 10^9 the probability that two specific distinct windows collide is about 1/M, so across n windows the expected number of spurious hits is roughly n/M — negligible for typical n. Using two independent moduli (double hashing) squares that probability.

Recognition

How to tell a problem wants this.

  • You must find all substrings of a fixed length that occur more than once (repeated DNA sequences, duplicate windows).
  • Several patterns of the same length are searched simultaneously — put their hashes in a Hash Set and check each window once.
  • 2D pattern matching, or comparing many substrings for equality where a suffix structure would be overkill.
“contiguous subarray” → Sliding Window“have you seen this before” → Hashing

Interactive visualization

Play, step, change the input. ← → and space work too.

a
a
0
b
1
x
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
y
11
pattern
a
0
b
1
c
2
a
3
b
4
y
5
1/17Use a rolling hash with base 256 modulo 101. h = base^(m-1) mod q = 36 is the weight of the window's leading character.
Current text windowVerifying a hash hitMatchSpurious hit (hash equal, text differs)
PseudocodeLearn Rabin–Karp →
1h = base^(m-1) mod q
2hp = hash(pattern); ht = hash(text[0..m-1])
3for s in 0 .. n-m:
4  if hp == ht:
5    verify text[s..s+m-1] == pattern  # rule out spurious hit
6  if s < n-m:
7    ht = (base*(ht - text[s]*h) + text[s+m]) mod q
Variables
base256
q101
h36
Complexity
best O(n + m)
avg O(n + m)
worst O(n · m)
space O(1)
Speed

Pseudocode

1high = B^(m-1) mod M
2hp = hash(p), ht = hash(t[0..m-1])
3for i in 0 .. n - m:
4  if ht == hp and t[i..i+m-1] == p: report i
5  if i < n - m:
6    ht = ((ht - t[i] * high) * B + t[i+m]) mod M

Implementations

1def rabin_karp(text: str, pattern: str) -> list[int]:
21 · Constants and edge cases
3    B = 256              # base larger than the alphabet
4    M = 1_000_000_007    # prime modulus (keeps ints small; correctness needs no mod)
5    n, m = len(text), len(pattern)
6    matches: list[int] = []
7    if m == 0 or m > n:
8        return matches
92 · Precompute B^(m-1) mod M
10    high = pow(B, m - 1, M)
113 · Hash the pattern and the first window
12    hp = ht = 0
13    for i in range(m):
14        hp = (hp * B + ord(pattern[i])) % M
15        ht = (ht * B + ord(text[i])) % M
16    for i in range(n - m + 1):
174 · Compare hashes, verify on a hit
18        if ht == hp and text[i:i + m] == pattern:
19            matches.append(i)
205 · Roll the window one character right
21        if i < n - m:
22            ht = ((ht - ord(text[i]) * high) * B + ord(text[i + m])) % M
23    return matches
Walkthrough
  1. Python integers are arbitrary precision, so the modulus is not needed for correctness — it is used to keep values small so each multiplication stays a single-word operation.
  2. pow(B, m - 1, M) is the three-argument built-in modular exponentiation, computed in C.
  3. ord(ch) converts a one-character string to its code point — the Python counterpart of charCodeAt.
  4. The verification text[i:i + m] == pattern slices (copies) m characters, but it only runs on hash hits.
  5. Python's % always returns a non-negative result for a positive modulus, so the roll can be written in one expression without the + M fix.
Complexity (this implementation)
time O(n + m) expected, O(n · m) worst · space O(1)

Without the modulus, ht would grow to m · 8 bits and every multiplication would become O(m) — still correct, but quadratic in practice.

Language notes
  • % in Python is a true modulo (result has the sign of the divisor), unlike C++/JS.
  • ord and chr convert between characters and code points; ord works on any Unicode code point, not just bytes.
  • For fixed-length duplicate detection the idiomatic Python shortcut is to hash slices with the built-in hash() into a set — simpler, but O(m) per window.
Common mistakes in this language
  • Dropping the modulus "because Python has big ints" and then wondering why the loop is quadratic.
  • Using text[i:i + m] in every iteration as the hash instead of rolling.
  • Passing pow(B, m - 1) % M (no third argument), which builds a huge intermediate before reducing.
Language differences that matter here
  • Integer size for hashing: C++ needs long long (products up to ~2^60); JS/TS number is a double, exact only below 2^53, so keep M < 2^30 and per-step products small or use BigInt; Python ints are unbounded, so the modulus is optional but keeps arithmetic fast.
  • Sign of %: C++ and JS/TS keep the dividend's sign, so (x % M + M) % M is required after the subtraction; Python's % already returns a non-negative value.
  • Character values: C++ char may be signed (cast to unsigned char), JS/TS charCodeAt gives 0–65535, Python ord gives a full code point.
  • Verification: std::string::compare(i, m, p), startsWith(p, i), and text[i:i+m] == p — only the Python version allocates a copy.

Complexity

Best
O(n + m)
Average
O(n + m)
Worst
O(n · m)
Space
O(1)

Worst case only under adversarial collisions; expected time is linear with a large prime modulus.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Finding repeated fixed-length substrings (hash every window into a set).
  • Matching several equal-length patterns at once with one pass over the text.
  • Substring equality checks in bulk — combine with Rolling Hash (Polynomial Hashing) prefix hashes to compare any two substrings in O(1).
Avoid it when

Alternatives

Knuth–Morris–Pratt (KMP)Z-AlgorithmNaive String MatchingAho–Corasick
Compare: KMP vs Rabin-Karp

Common mistakes

  • Skipping the character-by-character verification and trusting the hash — spurious hits then become wrong answers.
  • Negative intermediate values after subtracting t[i]·high; in C++, Java and JavaScript % keeps the sign, so add M first.
  • Overflow when multiplying two values near M in 64-bit languages — keep B·M and M² within range or reduce more often.
  • Choosing base B smaller than the alphabet size, which makes distinct strings map to the same polynomial before any modulus is applied.

Interview patterns

  • Repeated DNA sequences: hash every window of length 10 into a set.
  • Longest duplicate substring: binary search on the length, Rabin–Karp to test each length.
  • Count distinct substrings of a given length.
  • Check whether one string is a rotation of another via hashes of s + s.
Interview questions on this
Mock interviews

Example problems

Repeated DNA SequencesmediumFind the Index of the First Occurrenceeasy