Rabin–Karp substring search
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: []
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;}