
Multi-Pattern String Matching with Rabin-Karp Rolling Hashes
Naive substring search compares every pattern character by character at each text offset, degrading to O(n * m) worst-case time when repetitive prefixes force repeated backtracking. While single-pattern algorithms like Knuth-Morris-Pratt or Boyer-Moore solve single-needle matching in linear time, they require building dedicated automaton tables for each needle—making them awkward when an application must scan a document for dozens of fixed-length keywords, plagiarism fingerprints, or secret tokens in one pass.
The Rabin-Karp algorithm takes an algebraic approach by representing a substring of length m as a polynomial rolling hash modulo a large prime. Rather than recomputing the hash from scratch at every offset, sliding the window forward by one character subtracts the outgoing leading term, multiplies by the base, and adds the incoming character in constant O(1) time. By indexing all target patterns into a hash map beforehand, Rabin-Karp evaluates an entire family of patterns in O(n + m) expected time, verifying candidate hits with an exact string check to eliminate false positives from hash collisions.
Example
// Single-pattern rolling hash using safe integer arithmetic
function rabinKarpSearch(text, pattern) {
const n = text.length;
const m = pattern.length;
if (m === 0 || m > n) return [];
const BASE = 257;
const MOD = 1_000_000_007; // BASE * MOD (~2.57e11) stays well below Number.MAX_SAFE_INTEGER
let highPow = 1;
for (let i = 1; i < m; i += 1) {
highPow = (highPow * BASE) % MOD;
}
let patternHash = 0;
let windowHash = 0;
for (let i = 0; i < m; i += 1) {
patternHash = (patternHash * BASE + pattern.charCodeAt(i)) % MOD;
windowHash = (windowHash * BASE + text.charCodeAt(i)) % MOD;
}
const matches = [];
for (let i = 0; i <= n - m; i += 1) {
if (windowHash === patternHash && text.slice(i, i + m) === pattern) {
matches.push(i);
}
if (i < n - m) {
const outgoing = (text.charCodeAt(i) * highPow) % MOD;
windowHash = ((windowHash - outgoing + MOD) * BASE + text.charCodeAt(i + m)) % MOD;
}
}
return matches;
}
Implementation
/**
* Production-Ready Multi-Pattern Rabin-Karp Matcher
* Uses BigInt modular arithmetic to support large prime moduli without overflow,
* handles multiple equal-length patterns in a single pass, and groups distinct
* pattern lengths automatically.
*/
const HASH_BASE = 131_542_391n;
const HASH_MOD = 2_305_843_009_213_693_951n; // Mersenne prime 2^61 - 1
function computeHash(str, length) {
let hash = 0n;
for (let i = 0; i < length; i += 1) {
hash = (hash * HASH_BASE + BigInt(str.charCodeAt(i))) % HASH_MOD;
}
return hash;
}
function powerMod(base, exp, mod) {
let result = 1n;
let b = base % mod;
let e = exp;
while (e > 0n) {
if ((e & 1n) === 1n) {
result = (result * b) % mod;
}
b = (b * b) % mod;
e >>= 1n;
}
return result;
}
/**
* Finds all occurrences of every pattern in `patterns` inside `text`.
* Patterns sharing the same length are scanned together in a single linear pass.
*
* @param {string} text
* @param {readonly string[]} patterns
* @returns {Map<string, number[]>} Map of pattern -> sorted start indices
*/
export function findAllPatterns(text, patterns) {
const results = new Map();
const byLength = new Map();
for (const pattern of patterns) {
if (!pattern) continue;
if (!results.has(pattern)) {
results.set(pattern, []);
}
if (pattern.length > text.length) continue;
let bucket = byLength.get(pattern.length);
if (!bucket) {
bucket = new Map();
byLength.set(pattern.length, bucket);
}
const hash = computeHash(pattern, pattern.length);
const list = bucket.get(hash) ?? [];
if (!list.includes(pattern)) {
list.push(pattern);
bucket.set(hash, list);
}
}
for (const [m, hashBuckets] of byLength.entries()) {
const highPow = powerMod(HASH_BASE, BigInt(m - 1), HASH_MOD);
let windowHash = computeHash(text, m);
for (let i = 0; i <= text.length - m; i += 1) {
const candidates = hashBuckets.get(windowHash);
if (candidates) {
const slice = text.slice(i, i + m);
for (const candidate of candidates) {
// Exact comparison guarantees zero false positives on hash collision
if (slice === candidate) {
results.get(candidate).push(i);
}
}
}
if (i < text.length - m) {
const outgoing = (BigInt(text.charCodeAt(i)) * highPow) % HASH_MOD;
const incoming = BigInt(text.charCodeAt(i + m));
windowHash = (windowHash - outgoing + HASH_MOD) % HASH_MOD;
windowHash = (windowHash * HASH_BASE + incoming) % HASH_MOD;
}
}
}
return results;
}
Main Point: Rabin-Karp updates a polynomial hash in O(1) time per sliding window shift, allowing JavaScript applications to match dozens of patterns simultaneously in a single linear pass with exact collision verification.
Credits
Photo by drmakete lab on Unsplash