jsschools

Rabin-Karp Algorithm

Uses rolling polynomial hashing to find pattern occurrences in O(n + m) average time; especially useful for multi-pattern search and plagiarism detection.

Spec ↗

Syntax

rabinKarp(text, pattern)

Parameters

NameTypeRequiredDescription
text string Yes The string to search within (length n).
pattern string Yes The pattern to search for (length m).

Returns

number[] — Array of starting indices where pattern is found in text.

Examples

function rabinKarp(text, pattern) {
  const BASE = 31, MOD = 1_000_000_007n;
  const n = text.length, m = pattern.length;
  if (m > n) return [];

  const charCode = c => BigInt(c.charCodeAt(0) - 96);
  let patHash = 0n, winHash = 0n, power = 1n;

  for (let i = 0; i < m; i++) {
    patHash = (patHash * BigInt(BASE) + charCode(pattern[i])) % MOD;
    winHash = (winHash * BigInt(BASE) + charCode(text[i])) % MOD;
    if (i > 0) power = (power * BigInt(BASE)) % MOD;
  }

  const matches = [];
  for (let i = 0; i <= n - m; i++) {
    if (winHash === patHash && text.slice(i, i + m) === pattern)
      matches.push(i);
    if (i < n - m) {
      winHash = ((winHash - charCode(text[i]) * power) * BigInt(BASE) + charCode(text[i + m])) % MOD;
      if (winHash < 0n) winHash += MOD;
    }
  }
  return matches;
}

console.log(rabinKarp('abcaabcaa', 'abc'));
Output 
[ 0, 4 ]

// Hash collision: always verify with direct comparison (already done above)
function rabinKarp(text, pattern) {
  const BASE=31, MOD=1_000_000_007n, cc=c=>BigInt(c.charCodeAt(0)-96);
  const n=text.length, m=pattern.length;
  if(m>n) return [];
  let ph=0n, wh=0n, pw=1n;
  for(let i=0;i<m;i++){ph=(ph*BigInt(BASE)+cc(pattern[i]))%MOD;wh=(wh*BigInt(BASE)+cc(text[i]))%MOD;if(i>0)pw=(pw*BigInt(BASE))%MOD;}
  const res=[];
  for(let i=0;i<=n-m;i++){
    if(wh===ph&&text.slice(i,i+m)===pattern)res.push(i);
    if(i<n-m){wh=((wh-cc(text[i])*pw)*BigInt(BASE)+cc(text[i+m]))%MOD;if(wh<0n)wh+=MOD;}
  }
  return res;
}

// Pattern same as text
console.log(rabinKarp('aaaa', 'aa'));
Output 
[ 0, 1, 2 ]

Notes

| Case | Time | Space | |---------|-----------|-------| | Best | O(n + m) | O(1) | | Average | O(n + m) | O(1) | | Worst | O(nm) | O(1) | Worst case O(nm) occurs when every window is a hash collision (spurious hit), requiring a full string comparison each time. A strong hash (large prime modulus) makes this astronomically rare. The rolling hash removes the leading character and adds the trailing one in O(1), making each step O(1). Rabin-Karp is particularly attractive for **multiple pattern search**: precompute all pattern hashes and use a hash set for O(1) lookup per window.

See also