中文
devexamples

Rabin Karp Rolling Hash Pattern Match Typed

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

TypescriptData Fetching

Code

snippet
function rabinKarp(text: string, pattern: string): number[] {
  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: number[] = [];
  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