中文
devexamples

Rabin Karp Rolling Hash Pattern Match (JavaScript)

Find all occurrences of a pattern in text using the Rabin Karp algorithm with a rolling hash for O(n+m) average time complexity.

JavascriptData Fetching

Code

snippet
function rabinKarp(text, pattern) {
  const base = 256, mod = 101;
  const n = text.length, m = pattern.length;
  if (m === 0 || m > n) return [];
  let patHash = 0, txtHash = 0, h = 1;
  for (let i = 0; i < m - 1; i++) h = (h * base) % mod;
  for (let i = 0; i < m; i++) {
    patHash = (patHash * base + pattern.charCodeAt(i)) % mod;
    txtHash = (txtHash * base + text.charCodeAt(i)) % mod;
  }
  const result = [];
  for (let i = 0; i <= n - m; i++) {
    if (patHash === txtHash && text.slice(i, i + m) === pattern) result.push(i);
    if (i < n - m) {
      txtHash = (base * (txtHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod;
      if (txtHash < 0) txtHash += mod;
    }
  }
  return result;
}

Related Examples