1. Hash the pattern
Build a polynomial hash of the pattern once.
patternHash = (patternHash * base + pattern.charCodeAt(i)) % modTyporithm · hard
Rabin-Karp
▷ Interactive algorithm labrabin-karpstring-algorithmsrolling-hashhash-matchverify
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Rabin-Karp
String Algorithms
Slide a rolling hash over the text; on a hash match, verify the substring to rule out collisions.
Comparing the pattern at every position naively costs O(n·m).
A rolling hash updates in O(1) as the window slides: drop the leading char, add the new one.
Equal hashes only suggest a match, so a direct comparison confirms it and guards against collisions.
Preparing algorithm lab…
01
Rolling hash updates in O(1).
02
Hash equal → verify the substring.
03
Average O(n + m), worst O(n·m).
function rabinKarp(text, pattern) {
const n = text.length;
const m = pattern.length;
const base = 256;
const mod = 1000000007;
let patternHash = 0;
let windowHash = 0;
let power = 1;
for (let i = 0; i < m; i += 1) {
patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
windowHash = (windowHash * base + text.charCodeAt(i)) % mod;
if (i < m - 1) power = (power * base) % mod;
}
for (let i = 0; i + m <= n; i += 1) {
if (patternHash === windowHash && text.slice(i, i + m) === pattern) {
return i;
}
if (i + m < n) {
windowHash = ((windowHash - text.charCodeAt(i) * power) % mod + mod * mod) % mod;
windowHash = (windowHash * base + text.charCodeAt(i + m)) % mod;
}
}
return -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Top power
Precompute base^(m-1) to remove the leading character later.
power = (power * base) % mod3. Match then verify
Equal hashes are a hint; a direct compare rules out collisions.
if (patternHash === windowHash && text.slice(i, i + m) === pattern)4. Drop leading char
Subtract the outgoing character's contribution.
windowHash = ((windowHash - text.charCodeAt(i) * power) % mod + mod * mod) % mod5. Shift in new char
Multiply by the base and add the incoming character.
windowHash = (windowHash * base + text.charCodeAt(i + m)) % modA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.