Rabin-Karp Algorithm

The Rabin-Karp Algorithm is another pattern matching algorithm, but instead of character by character comparison, it uses hashing. You compute a hash of the pattern and a hash of each window of the text. If the hashes match, you do a full check to confirm. Smart.

Think of it like a fingerprint scanner. Instead of comparing every detail of a finger, you just check the fingerprint. If it matches, you are in. Rabin-Karp does the same thing with strings — hash first, verify only when hashes match.

The Rolling Hash Technique

The magic of Rabin-Karp is the rolling hash. When you slide the window one position, you do not recompute the hash from scratch. You subtract the contribution of the outgoing character and add the incoming one. This makes each window transition O(1).

function rabinKarp(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const base = 256;
  const mod = 1e9 + 7;
  let patternHash = 0;
  let textHash = 0;
  let basePow = 1;

  for (let i = 0; i < m - 1; i++) {
    basePow = (basePow * base) % mod;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
    textHash = (textHash * base + text.charCodeAt(i)) % mod;
  }

  const results = [];
  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) results.push(i);
    }
    if (i < n - m) {
      textHash = (textHash - text.charCodeAt(i) * basePow) % mod;
      textHash = (textHash * base + text.charCodeAt(i + m)) % mod;
      if (textHash < 0) textHash += mod;
    }
  }
  return results;
}

console.log(rabinKarp("AABAACAADAABAABA", "AABA"));

Average Case O(n + m)

On average, Rabin-Karp runs in O(n + m) time. The hash comparison is O(1), and most windows will not match, so you skip the O(m) verification. In the worst case (every window matches or every hash collides), it degrades to O(n × m), but this is extremely rare with a good hash function and large modulus.

The space complexity is O(1) — just a few variables for the hashes and the rolling calculation. This makes Rabin-Karp memory-efficient compared to KMP, which needs the LPS array.

Use Cases

Rabin-Karp really shines when you need to search for multiple patterns at once. Compute hashes for all patterns, then do a single pass over the text checking each window against all pattern hashes. This is much faster than running KMP multiple times.

It is also useful for plagiarism detection (finding matching passages across documents), detecting duplicates in streams, and checking for substrings with specific properties. The flexibility of the hash function makes it adaptable to many variations of the basic pattern matching problem.