Back to 20 Concepts
string-search • Advanced
Rabin-Karp Rolling Hash & Modular String Matching
Rabin-Karp computes a polynomial rolling hash over sliding string windows, enabling O(1) hash updates by shifting the window: Hash_new = ((Hash_old - OutChar * Base^(M-1)) * Base + InChar) % Modulo.
Intuitive Mental Model
The Odometer on a Car: When your car odometer rolls from 199 to 200, the computer subtracts the leading 100 and adds the new digit in a single turn.
C / TypeScript ImplementationHardware & Algorithmic Standard
function rollingHash(oldHash: number, outChar: string, inChar: string, highPower: number, base = 256, prime = 1000000007): number {
let h = (oldHash - outChar.charCodeAt(0) * highPower) % prime;
if (h < 0) h += prime;
h = (h * base + inChar.charCodeAt(0)) % prime;
return h;
}Key Architectural Takeaways
- •Average Time Complexity: O(N + M) expected time when using a large prime modulus.
- •Plagiarism Detection: Excellent for multi-pattern search with millions of documents.
Common Coding Mistake
Ignoring negative modulo results during rolling hash subtraction.
Optimal Solution
Always add the prime modulus if intermediate hash becomes negative: if (h < 0) h += prime.