Senior LevelData Structures & Algorithms
How does Rabin-Karp Hashing enable efficient substring search?
ā Interview Prompt: Explain Rabin-Karp rolling hash, polynomial hashing, spurious hits, worst-case O(NM) vs expected O(N+M), and double hashing.
Rabin-Karp computes a rolling hash for substrings, enabling $O(1)$ hash recomputation as the window slides, reducing pattern search to hash comparisons.
Polynomial Rolling Hash:
hash(s[i..i+M-1]) = Ī£ s[j] Ć B^(M-1-j) mod P
Rolling: Slide by removing leftmost character and adding rightmost:
newHash = (oldHash - s[i] Ć B^(M-1)) Ć B + s[i+M] (mod P)
Spurious Hits:
Hash collision (different strings with same hash) ā verify with actual string comparison.
ā¢
Expected: $O(N + M)$. Worst case (many collisions): $O(NM)$.
ā¢
Double hashing: Two independent hash functions reduces false positives dramatically.
Code Implementation Example
typescript
function rabinKarp(text: string, pattern: string): number[] {
const M = pattern.length, N = text.length;
const B = 31, P = 1_000_000_007n;
const Bn = BigInt(B);
const matches: number[] = [];
let patHash = 0n, winHash = 0n, power = 1n;
for (let i = 0; i < M; i++) {
patHash = (patHash * Bn + BigInt(pattern.charCodeAt(i))) % P;
winHash = (winHash * Bn + BigInt(text.charCodeAt(i))) % P;
if (i > 0) power = power * Bn % P;
}
for (let i = 0; i <= N - M; i++) {
if (winHash === patHash) {
if (text.slice(i, i + M) === pattern) matches.push(i); // verify hash hit
}
if (i < N - M) {
winHash = (winHash - BigInt(text.charCodeAt(i)) * power % P + P) % P;
winHash = (winHash * Bn + BigInt(text.charCodeAt(i + M))) % P;
}
}
return matches;
}š”Rabin-Karp rolling hash pattern search ā O(N+M) expected.
šÆ Interview Key Takeaway
Rabin-Karp's rolling hash extends to 2D pattern matching and substring duplicate detection. Double hashing reduces spurious hits to near-zero probability.
#DSA#Rabin-Karp#Rolling Hash#String Matching#Senior
Back to all Data Structures & Algorithms Questionsā