What is the Rabin-Karp algorithm?

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find any one of a set of pattern strings in a text. Its key innovation is the use of a rolling hash, which allows it to quickly calculate the hash value for the next substring given the hash value of the previous one.

What is a rolling hash?

A rolling hash is a hash function where the input is 'rolled' through a window of a fixed size. By using a clever mathematical formula, the hash value of the next window can be computed in constant time from the hash value of the current window, avoiding recalculation from scratch.

String Algorithms

Rabin-Karp Algorithm

An elegant string-searching algorithm that uses a rolling hash to quickly find a pattern within a text.

Rabin-Karp Implementation

This implementation demonstrates the rolling hash technique to efficiently search for a pattern in a text.

                            function rabinKarp(text, pattern) {
                            const d = 256; // number of characters in the input alphabet
                            const q = 101; // a prime number
                            const M = pattern.length;
                            const N = text.length;
                            let p = 0; // hash value for pattern
                            let t = 0; // hash value for text
                            let h = 1;
                            
                            for (let i = 0; i < M - 1; i++) { h = (h * d) % q; }
                            
                            for (let i = 0; i < M; i++) {
                            p = (d * p + pattern.charCodeAt(i)) % q;
                            t = (d * t + text.charCodeAt(i)) % q;
                            }
                            
                            for (let i = 0; i <= N - M; i++) {
                            if (p === t) {
                            let match = true;
                            for (let j = 0; j < M; j++) {
                            if (text[i + j] !== pattern[j]) { match = false; break; }
                            }
                            if (match) return i;
                            }
                            if (i < N - M) {
                            t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + M)) % q;
                            if (t < 0) t = t + q;
                            }
                            }
                            return -1;
                            }
                        

AI Coach Hint: The main weakness of Rabin-Karp is spurious hits (when hash values match but the strings don't). The choice of prime number `q` and base `d` is crucial to minimize these collisions. Be ready to discuss how you would handle frequent collisions in an interview.