Data Structures & Algorithms (DSA) Module 16 – String algorithms
Rolling hashes and Rabin-Karp
How a rolling hash moves to the next window in O(1), how Rabin-Karp finds every occurrence of a pattern with it, and how to keep collisions rare.
What you will learn
- Implement a rolling hash that updates in O(1) as a window slides
- Find every occurrence of a pattern with Rabin-Karp
- Estimate how often hashes collide and handle the collisions that happen
- Write exact hash arithmetic in Python, JavaScript, Java, C++ and Go
- Find the longest repeated substring with rolling hashes and binary search
Before you start
What you’ll learn · Before you start
What you will learn
- Implement a rolling hash that updates in O(1) as a window slides
- Find every occurrence of a pattern with Rabin-Karp
- Estimate how often hashes collide and handle the collisions that happen
- Write exact hash arithmetic in Python, JavaScript, Java, C++ and Go
- Find the longest repeated substring with rolling hashes and binary search
Before you start
On this page
Rabin-Karp finds a pattern of length m in a text of length n by comparing numbers instead of strings. It hashes the pattern once, then slides a window of m characters along the text and keeps the window’s hash up to date with a rolling hash: when the window moves one place, the hash drops the character that leaves, shifts by one power of the base and adds the character that enters, a few arithmetic operations whatever the value of m. Only a window whose hash equals the pattern’s is compared character by character, because different strings can share a hash. With a large prime modulus and a random base such false alarms are rare, and the search takes O(n + m) expected time. Karp and Rabin published the method in 1987. This lesson rolls a hash by hand, counts collisions for four moduli on a million DNA bases, keeps the arithmetic exact in five languages and finds the longest repeated stretch of a genome.
Comparing hashes instead of strings
The task: given a text and a pattern, return every start index i at which the text continues with the pattern,
overlapping occurrences included, so "aa" occurs in "aaaa" at 0, 1 and 2. The direct method tries every start and
compares characters from left to right until one differs. That can cost (n − m + 1) × m comparisons, because each
start may read almost the whole pattern before it fails.
Hashing changes what one start costs. Treat each window of m characters as a number, its polynomial hash from the hashing module: the character codes are the digits of a number in base B, reduced modulo a prime M. Two windows with different hashes certainly differ, so a start whose hash differs from the pattern’s is rejected with a single comparison of two numbers. The catch is computing the hash of every window: hashing each one from scratch reads m characters again and wins nothing. The rolling update removes that cost.
A rolling hash, worked by hand
Take the digits 5 3 1 2 1 1 8 4 as the text and 1 1 8 as the pattern. The digits are their own codes, the base is 10 and the modulus 97, so every hash can be checked on paper. Write h for the hash of the current window. When the window moves one place, three steps give the next hash:
Subtract the leaving digit times its weight, B^(m−1) mod M, which is 10² mod 97 = 3 here; multiply by the base; add the entering digit. The weight is computed once, before the scan.
One slide of the window, in three operations
Text description of the diagram
The diagram runs from top to bottom, for the digits 5 3 1 2 1 1 8 4 with base 10 and modulus 97.
- The first window, 5 3 1, has the hash 531 mod 97 = 46.
- Drop the leading digit: subtract 5 times its weight. The weight of the first of three digits is 10² mod 97 = 3, so 46 − 15 = 31.
- Shift one place: multiply by the base, 31 × 10 = 310.
- Add the new digit 2: 312, and 312 mod 97 = 21. That is the hash of the new window 3 1 2, found without reading its digits again.
- The pattern 1 1 8 also hashes to 21, so the digits are compared. They differ, so this window is a spurious hit and is skipped. The real occurrence comes three windows later.
The program below prints every step, and checks each rolled hash against the window’s hash computed from scratch:
# Rabin-Karp by hand: the digits are their own codes, the base is 10 and the modulus 97, so every hash is
# small enough to check on paper. Each window's hash is rolled from the previous one, never recomputed.
TEXT = "53121184"
PATTERN = "118"
BASE, MOD = 10, 97
m = len(PATTERN)
high = pow(BASE, m - 1, MOD) # the weight of the leading digit: 10**2 mod 97
def full_hash(s):
h = 0
for ch in s:
h = (h * BASE + int(ch)) % MOD
return h
target = full_hash(PATTERN)
print(f"pattern {PATTERN}: hash {target}; weight of the leading digit 10^{m - 1} mod {MOD} = {high}")
h = full_hash(TEXT[:m])
print(f"window 0 {TEXT[:m]}: hashed from scratch = {h}")
for i in range(1, len(TEXT) - m + 1):
out, new = int(TEXT[i - 1]), int(TEXT[i + m - 1])
rolled = ((h - out * high) * BASE + new) % MOD
window = TEXT[i:i + m]
assert rolled == full_hash(window) # rolling gives the same hash as hashing the window from scratch
print(f"window {i} {window}: (({h} - {out}*{high}) * {BASE} + {new}) mod {MOD} = {rolled}")
h = rolled
print("hash hits, then the digits compared:")
h = full_hash(TEXT[:m])
for i in range(len(TEXT) - m + 1):
if i > 0:
h = ((h - int(TEXT[i - 1]) * high) * BASE + int(TEXT[i + m - 1])) % MOD
if h == target:
window = TEXT[i:i + m]
verdict = "occurrence" if window == PATTERN else "spurious hit: same hash, different digits"
print(f" window {i} {window}: {verdict}")Output
pattern 118: hash 21; weight of the leading digit 10^2 mod 97 = 3 window 0 531: hashed from scratch = 46 window 1 312: ((46 - 5*3) * 10 + 2) mod 97 = 21 window 2 121: ((21 - 3*3) * 10 + 1) mod 97 = 24 window 3 211: ((24 - 1*3) * 10 + 1) mod 97 = 17 window 4 118: ((17 - 2*3) * 10 + 8) mod 97 = 21 window 5 184: ((21 - 1*3) * 10 + 4) mod 97 = 87 hash hits, then the digits compared: window 1 312: spurious hit: same hash, different digits window 4 118: occurrence
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 rolling_digits.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Two windows hash to 21, the pattern’s hash. Window 4, 1 1 8, is the occurrence. Window 1, 3 1 2, is a spurious hit: 312 and 118 differ by 194 = 2 × 97, so they leave the same remainder. That is why Rabin-Karp compares the characters before it reports a match. With a modulus of 97, a window shares the pattern’s hash about once in 97 tries; the rest of the lesson makes that chance negligible.
Rabin-Karp in Python
The full search uses Python’s character codes, ord, a large prime modulus M = 2⁶¹ − 1 and a base drawn at random
on every call. pow(base, m - 1, M) computes the weight of the first character without building a huge number:
import random
MOD = (1 << 61) - 1 # a prime: the hash of any string lies in 0 .. MOD - 1
def rabin_karp(text, pattern, rng=random):
"""Start index of every occurrence of pattern in text, overlapping ones included (pattern not empty)."""
n, m = len(text), len(pattern)
if m > n:
return []
base = rng.randrange(256, MOD - 1) # a fresh random base on every call
high = pow(base, m - 1, MOD) # the weight of the window's first character
target = h = 0
for i in range(m):
target = (target * base + ord(pattern[i])) % MOD
h = (h * base + ord(text[i])) % MOD
found = []
for i in range(n - m + 1):
# Equal hashes only suggest a match: compare the characters before reporting one.
if h == target and text[i:i + m] == pattern:
found.append(i)
if i + m < n: # roll: drop text[i], shift by one place, add text[i + m]
h = ((h - ord(text[i]) * high) * base + ord(text[i + m])) % MOD
return found
rng = random.Random(7) # seeded, so the recorded output repeats; real code uses the default generator
print(rabin_karp("a tatkal ticket, a tatkal fare, a tatkal queue", "tatkal", rng))
print(rabin_karp("aaaaa", "aa", rng)) # occurrences may overlap
print(rabin_karp("abc", "abcd", rng)) # a pattern longer than the text occurs nowhere
dna = "".join(rng.choices("ACGT", k=1_000_000))
hits = rabin_karp(dna, "TATAAA", rng)
print(f"TATAAA in 1,000,000 random bases: {len(hits)} occurrences, the first at {hits[:3]}")
expected = [i for i in range(len(dna) - 5) if dna.startswith("TATAAA", i)]
print("same as checking every position:", hits == expected)Output
[2, 19, 34] [0, 1, 2, 3] [] TATAAA in 1,000,000 random bases: 245 occurrences, the first at [1234, 2842, 3226] same as checking every position: True
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 rabin_karp.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
It finds “tatkal” three times, the overlapping occurrences of “aa” in “aaaaa”, and nothing when the pattern is longer
than the text. In a million random DNA bases, the promoter-like motif TATAAA occurred 245 times, close to the
10⁶ ÷ 4⁶ ≈ 244 that chance predicts, and checking every start directly gave the same list. Two details carry the correctness.
The comparison text[i:i + m] == pattern runs only when the hashes agree, so a spurious hit costs time but never a
wrong answer. And Python’s % never returns a negative number when M is positive, so the subtraction in the update
needs no correction.
What it costs: usually linear, sometimes not
Hashing the pattern and the first window costs O(m). Each later window costs O(1) to roll and O(1) to compare two numbers. The characters compared on hash hits are the only other work: m for every occurrence, and a few for every spurious hit. The next program counts character comparisons of the direct search and of Rabin-Karp on three texts:
# Character comparisons of the naive search and of Rabin-Karp on three texts. The naive search tries every start
# and compares left to right until a mismatch; Rabin-Karp compares characters only where the hashes agree.
import random
MOD = (1 << 61) - 1
rng = random.Random(5) # seeded, so the recorded output repeats
def naive(text, pattern):
n, m = len(text), len(pattern)
found, compared = [], 0
for i in range(n - m + 1):
k = 0
while k < m:
compared += 1
if text[i + k] != pattern[k]:
break
k += 1
if k == m:
found.append(i)
return found, compared
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
base = rng.randrange(256, MOD - 1)
high = pow(base, m - 1, MOD)
target = h = 0
for i in range(m):
target = (target * base + ord(pattern[i])) % MOD
h = (h * base + ord(text[i])) % MOD
found, compared = [], 0
for i in range(n - m + 1):
if h == target:
k = 0
while k < m:
compared += 1
if text[i + k] != pattern[k]:
break
k += 1
if k == m:
found.append(i)
if i + m < n:
h = ((h - ord(text[i]) * high) * base + ord(text[i + m])) % MOD
return found, compared
cases = [
("random DNA, n = 20,000, m = 200", "".join(rng.choices("ACGT", k=20_000)), "".join(rng.choices("ACGT", k=200))),
("a * 20,000 against a * 199 + b", "a" * 20_000, "a" * 199 + "b"),
("a * 20,000 against a * 200", "a" * 20_000, "a" * 200),
]
for name, text, pattern in cases:
(f1, c1), (f2, c2) = naive(text, pattern), rabin_karp(text, pattern)
assert f1 == f2
rolls = len(text) - len(pattern)
print(f"{name}: {len(f1):,} occurrences; naive compares {c1:,} characters;"
f" Rabin-Karp rolls its hash {rolls:,} times and compares {c2:,}")Output
random DNA, n = 20,000, m = 200: 0 occurrences; naive compares 26,308 characters; Rabin-Karp rolls its hash 19,800 times and compares 0 a * 20,000 against a * 199 + b: 0 occurrences; naive compares 3,960,200 characters; Rabin-Karp rolls its hash 19,800 times and compares 0 a * 20,000 against a * 200: 19,801 occurrences; naive compares 3,960,200 characters; Rabin-Karp rolls its hash 19,800 times and compares 3,960,200
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 worst_cases.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
| Text and pattern | Direct search compares | Rabin-Karp rolls, compares |
|---|---|---|
| Random DNA, 200 random bases | 26,308 | 19,800, 0 |
| 20,000 a, then 199 a and a b | 3,960,200 | 19,800, 0 |
| 20,000 a, then 200 a | 3,960,200 | 19,800, 3,960,200 |
On random text the direct search is cheap, because at almost every start the first or second character already differs from the pattern. On the second text it reads 200 characters at every start, while Rabin-Karp rejects every start by its hash. The third case defeats both: the pattern occurs at all 19,801 starts and each occurrence is verified in full, O(nm) in all. So the expected cost is O(n + m) plus m for each occurrence reported. The next lesson’s Knuth-Morris-Pratt algorithm stays O(n + m) even then, because it reuses what earlier comparisons established instead of checking each occurrence from scratch.
How often equal hashes lie
For two different strings of length m, the difference of their hashes is a polynomial in B of degree at most m − 1. Modulo a prime, such a polynomial has at most m − 1 roots, so a base chosen at random makes the two strings collide with probability at most about (m − 1)/M. Over all n − m + 1 windows, the expected number of spurious hits is at most about n·m/M, and for random text it is close to n/M. The run below hashes the same million random bases with four choices of modulus and counts what happened:
# How often do equal hashes lie? One random DNA string of 1,000,000 bases, the pattern TATAAA, and four choices of
# modulus, each with a random base. A spurious hit is a window whose hash equals the pattern's although its bases
# differ; each one costs at least one character comparison before it is thrown away.
import random
rng = random.Random(11) # seeded, so the recorded output repeats
dna = "".join(rng.choices("ACGT", k=1_000_000))
pattern = "TATAAA"
n, m = len(dna), len(pattern)
codes = [ord(c) for c in dna]
pcodes = [ord(c) for c in pattern]
def window_hashes(base, mod):
"""The hash of every window of length m, each rolled from the one before."""
high = pow(base, m - 1, mod)
h = 0
for c in codes[:m]:
h = (h * base + c) % mod
out = [h]
for i in range(m, n):
h = ((h - codes[i - m] * high) * base + codes[i]) % mod
out.append(h)
return out
def pattern_hash(base, mod):
h = 0
for c in pcodes:
h = (h * base + c) % mod
return h
def verify(i):
"""Compares the window at i with the pattern: (equal, characters compared)."""
for k in range(m):
if codes[i + k] != pcodes[k]:
return False, k + 1
return True, m
def report(name, hits, expected):
true = compared = 0
impostors = set()
for i in hits:
equal, cost = verify(i)
compared += cost
true += equal
if not equal:
impostors.add(dna[i:i + m])
spurious = len(hits) - true
print(f"{name}: {len(hits):,} hash hits = {true} occurrences + {spurious:,} spurious"
f" ({len(impostors)} different strings); {compared:,} characters compared; {expected}")
print(f"{n - m + 1:,} windows of {m} bases; {4 ** m:,} different windows are possible")
for name, mod in (("M = 1,009", 1_009), ("M = 10^9 + 7", 1_000_000_007), ("M = 2^61 - 1", (1 << 61) - 1)):
base = rng.randrange(256, mod - 1)
target = pattern_hash(base, mod)
hits = [i for i, h in enumerate(window_hashes(base, mod)) if h == target]
report(name, hits, f"expected spurious about {(n - m + 1) / mod:.3g}")
m1, m2 = 1_000_000_007, 998_244_353
b1, b2 = rng.randrange(256, m1 - 1), rng.randrange(256, m2 - 1)
t1, t2 = pattern_hash(b1, m1), pattern_hash(b2, m2)
both = [i for i, (x, y) in enumerate(zip(window_hashes(b1, m1), window_hashes(b2, m2))) if x == t1 and y == t2]
report("two moduli, 10^9 + 7 and 998,244,353", both, f"expected spurious about {(n - m + 1) / (m1 * m2):.3g}")Output
999,995 windows of 6 bases; 4,096 different windows are possible M = 1,009: 1,500 hash hits = 256 occurrences + 1,244 spurious (5 different strings); 2,780 characters compared; expected spurious about 991 M = 10^9 + 7: 256 hash hits = 256 occurrences + 0 spurious (0 different strings); 1,536 characters compared; expected spurious about 0.001 M = 2^61 - 1: 256 hash hits = 256 occurrences + 0 spurious (0 different strings); 1,536 characters compared; expected spurious about 4.34e-13 two moduli, 10^9 + 7 and 998,244,353: 256 hash hits = 256 occurrences + 0 spurious (0 different strings); 1,536 characters compared; expected spurious about 1e-12
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 collisions.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
With M = 1,009 there were 1,500 hash hits for 256 occurrences, so 1,244 windows were checked for nothing. The prediction was about 991. The gap is the luck of one base: only 4,096 different windows of six bases exist, this base sent 5 of them to the pattern’s hash, and each occurs about 250 times. With M = 10⁹ + 7, M = 2⁶¹ − 1, or two moduli near 10⁹ used together, which acts like one modulus near 10¹⁸, no spurious hit happened, and the 1,536 characters compared are exactly 256 occurrences of 6 characters.
Two ways to use these numbers:
- Verify every hit, as this lesson does. Every reported match is then right, and only the running time depends on luck. Choose M so that n·m/M is far below 1.
- Trust the hash and skip the comparison when a rare wrong answer is acceptable and the verification would be expensive, for example when comparing two long files by their fingerprints. Then M must be large enough that the error probability, about n·m/M, is tiny: 2⁶¹ − 1, or two independent moduli near 10⁹.
Always draw the base at random when the program starts. A fixed, published base lets anyone construct strings that collide on purpose, as the lesson on hash functions and flooding showed.
Exact arithmetic in five languages
Python’s integers have unlimited precision, so h * base is always exact, just slower when the numbers grow. The
other four languages need two rules.
Keep every product exact. A hash below M times a base below M is below M². With M = 10⁹ + 7 that is about 10¹⁸,
which fits in a 64-bit integer, whose limit is about 9.2 × 10¹⁸, so long in Java, std::int64_t in C++ and int64
in Go are exact. JavaScript numbers are doubles and represent integers exactly only up to Number.MAX_SAFE_INTEGER,
2⁵³ − 1, about 9 × 10¹⁵:
// JavaScript numbers are doubles: integers are exact only up to Number.MAX_SAFE_INTEGER = 2^53 - 1. A rolling hash
// multiplies a hash below M by a base below M, so with M = 10^9 + 7 the products reach about 10^18 and lose their
// last digits. The same search is run three ways on one text.
const P = 1_000_000_007;
console.log(`MAX_SAFE_INTEGER = ${Number.MAX_SAFE_INTEGER}`);
console.log(`(P - 1) * (P - 1) as a number: ${(P - 1) * (P - 1)}`);
console.log(`(P - 1) * (P - 1) as a BigInt: ${BigInt(P - 1) * BigInt(P - 1)}`);
// A text of 200,000 letters from a seeded generator (the product stays below 2^47, so it is exact).
let seed = 12345;
const next = () => (seed = (seed * 48271) % 2147483647);
let text = '';
for (let i = 0; i < 200_000; i++) text += 'abcd'[next() % 4];
const pattern = 'dabbadcabcaddcab'; // 16 letters, copied into the text at 10 places
for (let k = 0; k < 10; k++) {
const at = 7_000 + k * 19_000;
text = text.slice(0, at) + pattern + text.slice(at + pattern.length);
}
const base = 256 + (next() % (P - 300)); // a large base, as a random base below P usually is
function searchNumber(mod, b) {
const m = pattern.length;
let high = 1;
for (let i = 1; i < m; i++) high = (high * b) % mod;
let target = 0;
let h = 0;
for (let i = 0; i < m; i++) {
target = (target * b + pattern.charCodeAt(i)) % mod;
h = (h * b + text.charCodeAt(i)) % mod;
}
const found = [];
for (let i = 0; i + m <= text.length; i++) {
if (h === target && text.startsWith(pattern, i)) found.push(i);
if (i + m < text.length) {
const out = (text.charCodeAt(i) * high) % mod;
h = ((((h - out) % mod) + mod) % mod * b + text.charCodeAt(i + m)) % mod;
}
}
return found;
}
function searchBigInt(mod, b) {
const m = pattern.length;
let high = 1n;
for (let i = 1; i < m; i++) high = (high * b) % mod;
let target = 0n;
let h = 0n;
for (let i = 0; i < m; i++) {
target = (target * b + BigInt(pattern.charCodeAt(i))) % mod;
h = (h * b + BigInt(text.charCodeAt(i))) % mod;
}
const found = [];
for (let i = 0; i + m <= text.length; i++) {
if (h === target && text.startsWith(pattern, i)) found.push(i);
if (i + m < text.length) {
const out = (BigInt(text.charCodeAt(i)) * high) % mod;
h = ((((h - out) % mod) + mod) % mod * b + BigInt(text.charCodeAt(i + m))) % mod;
}
}
return found;
}
const truth = [];
for (let i = text.indexOf(pattern); i !== -1; i = text.indexOf(pattern, i + 1)) truth.push(i);
const safe = 94_906_249; // the largest prime M with (M - 1) * (M - 1) + 65535 below 2^53
const runs = [
['numbers, M = 10^9 + 7', searchNumber(P, base)],
['BigInt, M = 10^9 + 7', searchBigInt(BigInt(P), BigInt(base))],
['numbers, M = 94,906,249', searchNumber(safe, base % safe)],
];
console.log(`pattern ${pattern} occurs ${truth.length} times: ${truth.join(', ')}`);
for (const [name, found] of runs) {
const missed = truth.filter((i) => !found.includes(i)).length;
console.log(`${name}: found ${found.length}, missed ${missed}`);
}Output
MAX_SAFE_INTEGER = 9007199254740991 (P - 1) * (P - 1) as a number: 1000000012000000000 (P - 1) * (P - 1) as a BigInt: 1000000012000000036 pattern dabbadcabcaddcab occurs 10 times: 7000, 26000, 45000, 64000, 83000, 102000, 121000, 140000, 159000, 178000 numbers, M = 10^9 + 7: found 0, missed 10 BigInt, M = 10^9 + 7: found 10, missed 0 numbers, M = 94,906,249: found 10, missed 0
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node precision.mjs
Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
The product (10⁹ + 6)² came out as …012000000000 instead of …012000000036, and with hashes rounded like that the number version missed all 10 copies of the pattern. BigInt found them, and so did plain numbers with M = 94,906,249, the largest prime for which a hash times a base plus a character code stays below 2⁵³. A smaller M means more spurious hits, about n/M of them for random text, so a long text can use two such moduli at once.
Keep every remainder non-negative. Python’s % takes the sign of the divisor, but in Java, C++, Go and JavaScript
the remainder takes the sign of the dividend: −7 % 5 is −2. The rolling subtraction often goes below zero, so these
versions add M before reducing again:
Python · five/rabin_karp.py
# Rabin-Karp in Python (the same program in five languages). M = 1,000,000,007 and the base 911,382,323 are fixed so
# that every language prints the same hashes; real code picks the base at random when it starts.
M = 1_000_000_007
B = 911_382_323
def poly_hash(s):
h = 0
for ch in s:
h = (h * B + ord(ch)) % M
return h
def rabin_karp(text, pattern):
"""Start index of every occurrence of pattern in text, overlapping ones included."""
n, m = len(text), len(pattern)
if m > n:
return []
high = pow(B, m - 1, M)
target, h = poly_hash(pattern), poly_hash(text[:m])
found = []
for i in range(n - m + 1):
if h == target and text[i:i + m] == pattern:
found.append(i)
if i + m < n:
# Python's % never returns a negative number for a positive M, so no correction is needed.
h = ((h - ord(text[i]) * high) * B + ord(text[i + m])) % M
return found
def generated(n):
"""n bases from the minimal standard generator, the same in every language."""
x, out = 1, []
for _ in range(n):
x = x * 48271 % 2147483647
out.append("ACGT"[x % 4])
return "".join(out)
print("-7 % 5 =", -7 % 5)
print("hash of TATAAA =", poly_hash("TATAAA"))
dna = generated(300_000)
for pattern in ("TATAAA", "GATTACA", "AAAAA"):
found = rabin_karp(dna, pattern)
print(f"{pattern}: {len(found)} occurrences, the first at {', '.join(map(str, found[:3]))}")Output
-7 % 5 = 3 hash of TATAAA = 175020890 TATAAA: 89 occurrences, the first at 3582, 6339, 6872 GATTACA: 19 occurrences, the first at 26583, 36051, 75163 AAAAA: 265 occurrences, the first at 1488, 3540, 4579
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 rabin_karp.py
JavaScript · five/rabin_karp.mjs
// Rabin-Karp in JavaScript (the same program in five languages). Hashes below M times a base below M reach about
// 10^18, beyond the 2^53 up to which numbers are exact, so the arithmetic is done with BigInt.
const M = 1_000_000_007n;
const B = 911_382_323n;
function polyHash(s) {
let h = 0n;
for (let i = 0; i < s.length; i++) h = (h * B + BigInt(s.charCodeAt(i))) % M;
return h;
}
/** Start index of every occurrence of pattern in text, overlapping ones included. */
function rabinKarp(text, pattern) {
const n = text.length;
const m = pattern.length;
if (m > n) return [];
let high = 1n;
for (let i = 1; i < m; i++) high = (high * B) % M;
const target = polyHash(pattern);
let h = polyHash(text.slice(0, m));
const found = [];
for (let i = 0; i + m <= n; i++) {
if (h === target && text.startsWith(pattern, i)) found.push(i);
if (i + m < n) {
// % keeps the sign of the left side in JavaScript: add M before reducing again.
const rest = (h - BigInt(text.charCodeAt(i)) * high) % M;
h = (((rest + M) % M) * B + BigInt(text.charCodeAt(i + m))) % M;
}
}
return found;
}
/** n bases from the minimal standard generator, the same in every language. */
function generated(n) {
let x = 1;
const out = [];
for (let k = 0; k < n; k++) {
x = (x * 48271) % 2147483647; // below 2^47: exact as a number
out.push('ACGT'[x % 4]);
}
return out.join('');
}
console.log(`-7 % 5 = ${-7 % 5}`);
console.log(`hash of TATAAA = ${polyHash('TATAAA')}`);
const dna = generated(300_000);
for (const pattern of ['TATAAA', 'GATTACA', 'AAAAA']) {
const found = rabinKarp(dna, pattern);
console.log(`${pattern}: ${found.length} occurrences, the first at ${found.slice(0, 3).join(', ')}`);
}Output
-7 % 5 = -2 hash of TATAAA = 175020890 TATAAA: 89 occurrences, the first at 3582, 6339, 6872 GATTACA: 19 occurrences, the first at 26583, 36051, 75163 AAAAA: 265 occurrences, the first at 1488, 3540, 4579
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node rabin_karp.mjs
Java · compiled/RabinKarp.java
// Rabin-Karp in Java (the same program in five languages). A hash below M times a base below M stays under 2^63, so
// long arithmetic is exact; % keeps the sign of its left side, so M is added before reducing again.
import java.util.ArrayList;
import java.util.List;
public class RabinKarp {
static final long M = 1_000_000_007L;
static final long B = 911_382_323L;
static long polyHash(String s, int length) {
long h = 0;
for (int i = 0; i < length; i++) h = (h * B + s.charAt(i)) % M;
return h;
}
/** Start index of every occurrence of pattern in text, overlapping ones included. */
static List<Integer> rabinKarp(String text, String pattern) {
int n = text.length(), m = pattern.length();
List<Integer> found = new ArrayList<>();
if (m > n) return found;
long high = 1;
for (int i = 1; i < m; i++) high = high * B % M;
long target = polyHash(pattern, m), h = polyHash(text, m);
for (int i = 0; i + m <= n; i++) {
if (h == target && text.startsWith(pattern, i)) found.add(i);
if (i + m < n) {
long rest = (h - text.charAt(i) * high % M + M) % M;
h = (rest * B + text.charAt(i + m)) % M;
}
}
return found;
}
/** n bases from the minimal standard generator, the same in every language. */
static String generated(int n) {
long x = 1;
StringBuilder out = new StringBuilder(n);
for (int k = 0; k < n; k++) {
x = x * 48271 % 2147483647;
out.append("ACGT".charAt((int) (x % 4)));
}
return out.toString();
}
public static void main(String[] args) {
System.out.println("-7 % 5 = " + (-7 % 5));
System.out.println("hash of TATAAA = " + polyHash("TATAAA", 6));
String dna = generated(300_000);
for (String pattern : new String[] {"TATAAA", "GATTACA", "AAAAA"}) {
List<Integer> found = rabinKarp(dna, pattern);
List<String> first = new ArrayList<>();
for (int i = 0; i < Math.min(3, found.size()); i++) first.add(String.valueOf(found.get(i)));
System.out.println(pattern + ": " + found.size() + " occurrences, the first at " + String.join(", ", first));
}
}
}C++ · compiled/rabin_karp.cpp
// Rabin-Karp in C++ (the same program in five languages). A hash below M times a base below M stays under 2^63, so
// std::int64_t arithmetic is exact; % keeps the sign of its left side, so M is added before reducing again.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
constexpr std::int64_t M = 1'000'000'007;
constexpr std::int64_t B = 911'382'323;
std::int64_t poly_hash(std::string_view s) {
std::int64_t h = 0;
for (unsigned char c : s) h = (h * B + c) % M;
return h;
}
// Start index of every occurrence of pattern in text, overlapping ones included.
std::vector<std::size_t> rabin_karp(std::string_view text, std::string_view pattern) {
const std::size_t n = text.size(), m = pattern.size();
std::vector<std::size_t> found;
if (m > n) return found;
std::int64_t high = 1;
for (std::size_t i = 1; i < m; ++i) high = high * B % M;
const std::int64_t target = poly_hash(pattern);
std::int64_t h = poly_hash(text.substr(0, m));
for (std::size_t i = 0; i + m <= n; ++i) {
if (h == target && text.substr(i, m) == pattern) found.push_back(i);
if (i + m < n) {
const std::int64_t out = static_cast<unsigned char>(text[i]);
const std::int64_t rest = (h - out * high % M + M) % M;
h = (rest * B + static_cast<unsigned char>(text[i + m])) % M;
}
}
return found;
}
// n bases from the minimal standard generator, the same in every language.
std::string generated(std::size_t n) {
std::int64_t x = 1;
std::string out;
out.reserve(n);
for (std::size_t k = 0; k < n; ++k) {
x = x * 48271 % 2147483647;
out.push_back("ACGT"[x % 4]);
}
return out;
}
int main() {
std::cout << "-7 % 5 = " << (-7 % 5) << '\n';
std::cout << "hash of TATAAA = " << poly_hash("TATAAA") << '\n';
const std::string dna = generated(300'000);
for (std::string_view pattern : {"TATAAA", "GATTACA", "AAAAA"}) {
const auto found = rabin_karp(dna, pattern);
std::cout << pattern << ": " << found.size() << " occurrences, the first at ";
for (std::size_t i = 0; i < found.size() && i < 3; ++i) std::cout << (i ? ", " : "") << found[i];
std::cout << '\n';
}
}Go · compiled/rabin_karp.go
// Rabin-Karp in Go (the same program in five languages). A hash below M times a base below M stays under 2^63, so
// int64 arithmetic is exact; % keeps the sign of its left side, so M is added before reducing again.
package main
import (
"fmt"
"strings"
)
const (
M int64 = 1_000_000_007
B int64 = 911_382_323
)
func polyHash(s string) int64 {
var h int64
for i := 0; i < len(s); i++ {
h = (h*B + int64(s[i])) % M
}
return h
}
// rabinKarp returns the start index of every occurrence of pattern in text, overlapping ones included.
func rabinKarp(text, pattern string) []int {
n, m := len(text), len(pattern)
var found []int
if m > n {
return found
}
high := int64(1)
for i := 1; i < m; i++ {
high = high * B % M
}
target, h := polyHash(pattern), polyHash(text[:m])
for i := 0; i+m <= n; i++ {
if h == target && text[i:i+m] == pattern {
found = append(found, i)
}
if i+m < n {
rest := (h - int64(text[i])*high%M + M) % M
h = (rest*B + int64(text[i+m])) % M
}
}
return found
}
// generated returns n bases from the minimal standard generator, the same in every language.
func generated(n int) string {
x := int64(1)
var out strings.Builder
out.Grow(n)
for k := 0; k < n; k++ {
x = x * 48271 % 2147483647
out.WriteByte("ACGT"[x%4])
}
return out.String()
}
func main() {
a, b := -7, 5
fmt.Println("-7 % 5 =", a%b)
fmt.Println("hash of TATAAA =", polyHash("TATAAA"))
dna := generated(300_000)
for _, pattern := range []string{"TATAAA", "GATTACA", "AAAAA"} {
found := rabinKarp(dna, pattern)
first := make([]string, 0, 3)
for _, i := range found[:min(3, len(found))] {
first = append(first, fmt.Sprint(i))
}
fmt.Printf("%s: %d occurrences, the first at %s\n", pattern, len(found), strings.Join(first, ", "))
}
}Runs on this device, in your browser. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
from session import run, versions
# RabinKarp.java runs straight from its source file; rabin_karp.cpp is built with the sanitizers on; go run builds
# rabin_karp.go.
versions("java -version", "clang++ --version", "go version")
run("""
java RabinKarp.java
clang++ -std=c++23 -O1 -Wall -Wextra -fsanitize=address,undefined rabin_karp.cpp -o rabin_karp && ./rabin_karp
go run rabin_karp.go
""")Output
# openjdk version "25.0.4.1" LTS # Apple clang version 21.0.0 (clang-2100.3.34.2) # go version go1.27.1 darwin/arm64 $ java RabinKarp.java -7 % 5 = -2 hash of TATAAA = 175020890 TATAAA: 89 occurrences, the first at 3582, 6339, 6872 GATTACA: 19 occurrences, the first at 26583, 36051, 75163 AAAAA: 265 occurrences, the first at 1488, 3540, 4579 $ clang++ -std=c++23 -O1 -Wall -Wextra -fsanitize=address,undefined rabin_karp.cpp -o rabin_karp && ./rabin_karp -7 % 5 = -2 hash of TATAAA = 175020890 TATAAA: 89 occurrences, the first at 3582, 6339, 6872 GATTACA: 19 occurrences, the first at 26583, 36051, 75163 AAAAA: 265 occurrences, the first at 1488, 3540, 4579 $ go run rabin_karp.go -7 % 5 = -2 hash of TATAAA = 175020890 TATAAA: 89 occurrences, the first at 3582, 6339, 6872 GATTACA: 19 occurrences, the first at 26583, 36051, 75163 AAAAA: 265 occurrences, the first at 1488, 3540, 4579
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 rk_session.py
All five print the same hash for TATAAA and the same occurrences in 300,000 bases from the minimal standard generator: 89 of TATAAA, 19 of GATTACA and 265 of the overlapping AAAAA. The base is fixed here so that the five outputs can be compared; real code draws it at random. One more difference matters for text that is not ASCII: Python indexes code points, Java and JavaScript UTF-16 code units, and C++ and Go bytes. In “नमस्ते नमस्ते” the second word starts at index 7 in Python, Java and JavaScript but at byte 19 in C++ and Go, because each Devanagari character takes three bytes in UTF-8.
The longest repeated substring, by binary search on the length
Rolling hashes also compare many substrings with each other, not just with one pattern. Suppose you want the longest stretch of a genome that occurs twice. If some stretch of length L occurs twice, then so does its first L − 1 characters, so the answer to “does a length-L stretch repeat?” is yes up to the answer and no after it, which is exactly what binary search needs. Each check hashes every window of length L in one pass over the text and keeps a set of the hashes seen, comparing characters whenever a hash comes back:
# The longest substring that occurs twice, by binary search on its length: if some length L repeats, so does every
# shorter length, so "does a length-L window repeat?" is false-then-true, and each check is one pass of rolling
# hashes with a set of the hashes seen so far.
import random
MOD = (1 << 61) - 1
rng = random.Random(3) # seeded, so the recorded output repeats
def repeat_of_length(text, length, base):
"""Two starts i < j with equal windows of this length, or None. Windows are compared before they count."""
if length == 0:
return (0, 0)
high = pow(base, length - 1, MOD)
h = 0
for ch in text[:length]:
h = (h * base + ord(ch)) % MOD
seen = {} # hash -> starts with that hash
for i in range(len(text) - length + 1):
if i > 0:
h = ((h - ord(text[i - 1]) * high) * base + ord(text[i + length - 1])) % MOD
for j in seen.get(h, ()):
if text[j:j + length] == text[i:i + length]:
return (j, i)
seen.setdefault(h, []).append(i)
return None
def longest_repeat(text):
"""(length, first start, second start) of a longest substring that occurs at least twice."""
base = rng.randrange(256, MOD - 1)
lo, hi, best, rounds = 0, len(text) - 1, (0, 0), 0
while lo < hi: # invariant: length lo repeats, every length above hi does not
mid = (lo + hi + 1) // 2
rounds += 1
found = repeat_of_length(text, mid, base)
if found:
lo, best = mid, found
else:
hi = mid - 1
return lo, best[0], best[1], rounds
def brute_force(text):
n = len(text)
return max((k for i in range(n) for j in range(i + 1, n) for k in range(1, n - j + 1)
if text[i:i + k] == text[j:j + k]), default=0)
for _ in range(300): # checked against every pair of starts on short random strings
s = "".join(rng.choices("ab", k=rng.randint(1, 14)))
assert longest_repeat(s)[0] == brute_force(s), s
print("300 short strings: same lengths as the brute force")
genome = list(rng.choices("ACGT", k=50_000))
genome[40_000:40_300] = genome[10_000:10_300] # one stretch of 300 bases copied
genome = "".join(genome)
length, i, j, rounds = longest_repeat(genome)
print(f"50,000 bases: a stretch of {length} bases occurs at {i:,} and at {j:,}, found in {rounds} rounds")Output
300 short strings: same lengths as the brute force 50,000 bases: a stretch of 301 bases occurs at 10,000 and at 40,000, found in 15 rounds
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 longest_repeat.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
First the method agrees with a brute force that checks every pair of starts on 300 short strings. Then, in 50,000 random bases with one stretch of 300 copied from position 10,000 to 40,000, it reports 301 bases in 15 rounds: the base after each copy happens to be the same, which a correct method must count. Each round costs O(n) expected time, so the whole search costs O(n log n). Suffix arrays, later in this module, answer the same question without any hashing.
Practise: find every occurrence
Write the search yourself. The tests include texts of a million characters and one where every window holds the same letters as the pattern in another order.
Exercise · Medium · Python, JavaScript
Find every occurrence with Rabin-Karp
Write find_all(text, pattern) in find_all.py (JavaScript: findAll(text, pattern) in find_all.mjs). It returns the start index of every occurrence of pattern in text, from left to right, overlapping occurrences included: for "aaaa" and "aa" the answer is [0, 1, 2]. The pattern has at least one character; when it is longer than the text, return an empty list.
Use Rabin-Karp:
- Hash the pattern and the first window of the text with a polynomial hash,
s[0]·B^(m−1) + … + s[m−1]modulo a primeM, wheres[i]is the character code (ordin Python,charCodeAtin JavaScript, so JavaScript indices count UTF-16 code units). - Roll the window one place at a time in O(1): remove the leftmost character's term, multiply by
B, add the new character. - Report a window only after comparing its characters with the pattern, since different strings can share a hash.
Pick the base at random. In JavaScript keep every product below 2⁵³: with plain numbers, a prime below 94,906,250 such as 94,906,249 works, or use BigInt. The last two tests use texts of 1,000,000 characters. In one of them every window holds the same letters as the pattern in another order, so a hash that ignores the order of the characters matches everywhere, and only the comparison in step 3 keeps the answer right.
Python · Starter code · find_all.py
import random
def find_all(text, pattern):
"""Start index of every occurrence of pattern in text, overlapping ones included, found with Rabin-Karp."""
# Replace this line with your code.
return []The sample tests · test_find_all.py
import random
from find_all import find_all
def every_start(text, pattern):
return [i for i in range(len(text) - len(pattern) + 1) if text.startswith(pattern, i)]
def test_small_cases():
"""occurrences, overlaps, and patterns that do not occur"""
assert find_all("abracadabra", "abra") == [0, 7]
assert find_all("aaaa", "aa") == [0, 1, 2]
assert find_all("53121184", "118") == [4]
assert find_all("abc", "abcd") == []
assert find_all("abc", "x") == []
assert find_all("", "a") == []
assert find_all("नमस्ते नमस्ते", "नम") == [0, 7]
def test_random_texts():
"""300 random texts over two letters, against checking every start"""
rng = random.Random(4)
for _ in range(300):
text = "".join(rng.choices("ab", k=rng.randint(0, 40)))
pattern = "".join(rng.choices("ab", k=rng.randint(1, 5)))
assert find_all(text, pattern) == every_start(text, pattern), (text, pattern)
def test_million_random_characters():
"""1,000,000 random characters and a pattern of 12"""
rng = random.Random(9)
text = "".join(rng.choices("ACGT", k=1_000_000))
pattern = text[777_000:777_012]
assert find_all(text, pattern) == every_start(text, pattern)
def test_million_with_equal_letters():
"""'ab' * 500,000: every window of 5,000 has 2,500 of each letter, like the pattern, which never occurs"""
text = "ab" * 500_000
assert find_all(text, "a" * 2_500 + "b" * 2_500) == []
assert len(find_all(text, "bababa")) == 499_997JavaScript · Starter code · find_all.mjs
/** Start index of every occurrence of pattern in text, overlapping ones included, found with Rabin-Karp. */
export function findAll(text, pattern) {
// Replace this line with your code.
return [];
}The sample tests · find_all.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { findAll } from './find_all.mjs';
function everyStart(text, pattern) {
const out = [];
for (let i = 0; i + pattern.length <= text.length; i++) if (text.startsWith(pattern, i)) out.push(i);
return out;
}
function makeRandom(seed) {
return () => (seed = (seed * 48271) % 2147483647) / 2147483647;
}
test('occurrences, overlaps, and patterns that do not occur', () => {
assert.deepEqual(findAll('abracadabra', 'abra'), [0, 7]);
assert.deepEqual(findAll('aaaa', 'aa'), [0, 1, 2]);
assert.deepEqual(findAll('53121184', '118'), [4]);
assert.deepEqual(findAll('abc', 'abcd'), []);
assert.deepEqual(findAll('abc', 'x'), []);
assert.deepEqual(findAll('', 'a'), []);
assert.deepEqual(findAll('नमस्ते नमस्ते', 'नम'), [0, 7]);
});
test('300 random texts over two letters, against checking every start', () => {
const random = makeRandom(4);
for (let t = 0; t < 300; t++) {
let text = '';
const n = Math.floor(random() * 41);
for (let i = 0; i < n; i++) text += random() < 0.5 ? 'a' : 'b';
let pattern = '';
const m = 1 + Math.floor(random() * 5);
for (let i = 0; i < m; i++) pattern += random() < 0.5 ? 'a' : 'b';
assert.deepEqual(findAll(text, pattern), everyStart(text, pattern), `${text} ${pattern}`);
}
});
test('1,000,000 random characters and a pattern of 12', () => {
const random = makeRandom(9);
const parts = [];
for (let i = 0; i < 1_000_000; i++) parts.push('ACGT'[Math.floor(random() * 4)]);
const text = parts.join('');
const pattern = text.slice(777_000, 777_012);
assert.deepEqual(findAll(text, pattern), everyStart(text, pattern));
});
test("'ab' repeated 500,000 times: every window of 5,000 has 2,500 of each letter, like the pattern", () => {
const text = 'ab'.repeat(500_000);
assert.deepEqual(findAll(text, 'a'.repeat(2_500) + 'b'.repeat(2_500)), []);
assert.equal(findAll(text, 'bababa').length, 499_997);
});A hint
Keep high = B^(m−1) mod M, the weight of the window's first character. To move from the window at i to the one at i + 1: h = ((h − code(text[i]) · high) · B + code(text[i + m])) mod M. Python's % never returns a negative number for a positive M; in JavaScript, add M before taking % again.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
4 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
What is a rolling hash, and why can it move from one window of a text to the next in O(1) time?
A rolling hash is a hash of a fixed-length window that is updated as the window slides, instead of being recomputed. With the polynomial hash, the window’s characters are the digits of a number in base B, modulo a prime M. Moving the window one place changes that number in a predictable way: the leaving character’s term disappears, every other digit moves up one place, and the new character becomes the last digit. So the new hash is ((h − s_out · B^(m−1)) · B + s_in) mod M, three arithmetic operations with the weight B^(m−1) mod M computed once in advance. That is O(1) work per step whatever the window length m, against O(m) for hashing each window from scratch, which is what makes Rabin-Karp linear in expectation.
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Mid to senior
Your JavaScript Rabin-Karp passes its unit tests, which fix the base at 31, but in production, with a random base below M = 1,000,000,007, it misses matches. It uses plain numbers throughout. Explain the failure with numbers and give two fixes, with what each costs.
Key takeaways
- Rabin-Karp compares the hash of each window with the pattern’s hash and compares characters only when they agree.
- A rolling hash moves to the next window in O(1): subtract the leaving character times B^(m−1), multiply by B, add the entering character, all modulo M.
- Equal hashes do not prove equal strings: verify every hit, or accept a tiny error probability with a modulus near 10¹⁸ or two moduli near 10⁹.
- With a random base, two different strings of length m collide with probability at most about (m − 1)/M; the expected running time is O(n + m) plus m for every occurrence verified.
- In JavaScript keep products below 2⁵³ or use BigInt; in Java, C++, Go and JavaScript add M before taking a remainder that may be negative.
- Rolling hashes with binary search on the length find the longest repeated substring in O(n log n) expected time.
References
- Efficient randomized pattern-matching algorithms (R. M. Karp and M. O. Rabin, IBM Journal of Research and Development, volume 31, number 2) (IBM)
- Dictionary of Algorithms and Data Structures: Karp-Rabin (National Institute of Standards and Technology (NIST))
- Built-in functions: pow() with three arguments (Python Software Foundation)
- Expressions: binary arithmetic operations (the sign of %) (Python Software Foundation)
- Built-in types: numeric types (integers have unlimited precision) (Python Software Foundation)
- Number.MAX_SAFE_INTEGER (MDN Web Docs)
- BigInt (MDN Web Docs)
- Remainder (%) (MDN Web Docs)
- The Java Language Specification, Java SE 25: 15.17.3 Remainder Operator % (Oracle)
- Arithmetic operators: multiplicative operators and overflows (cppreference.com)
- The Go Programming Language Specification: integer operators (The Go Authors)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress