Rabin–Karp substring search

Medium

Problem

Find every index where the pattern occurs in the text, using a rolling hash: compare hashes first, and check characters only when the hashes match.

Example 1

Input:  text = "AABAACAADAABAABA", pattern = "AABA"
Output: [0, 9, 12]

Also asked as: Rabin Karp Algo

Test cases

Case 1

Input:    "AABAACAADAABAABA", "AABA"
Expected: [0,9,12]

Case 2

Input:    "aaaa", "aa"
Expected: [0,1,2]

Case 3

Input:    "abc", "d"
Expected: []

Case 4

Input:    "ab", "abc"
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Rolling hash

Time O(n + m) average, O(n·m) worstSpace O(1)

Hash the pattern and each length-m window of the text; roll the hash in O(1) per shift. On a hash match, verify char-by-char.

function rabinKarp(text, pat) {
const n = text.length, m = pat.length;
if (m > n) return [];
const B = 256, MOD = 1_000_000_007;
let pHash = 0, tHash = 0, pow = 1;
for (let i = 0; i < m - 1; i++) pow = (pow * B) % MOD;
for (let i = 0; i < m; i++) {
pHash = (pHash * B + pat.charCodeAt(i)) % MOD;
tHash = (tHash * B + text.charCodeAt(i)) % MOD;
}
const res = [];
for (let i = 0; i + m <= n; i++) {
if (pHash === tHash && text.slice(i, i + m) === pat) res.push(i);
if (i + m < n) {
tHash = ((tHash - text.charCodeAt(i) * pow) % MOD + MOD) % MOD;
tHash = (tHash * B + text.charCodeAt(i + m)) % MOD;
}
}
return res;
}