Как работает алгоритм Рабина–Карпа и полиномиальное хеширование строк?

Рабин–Карп сравнивает не строки, а их полиномиальные хеши: хеш окна текста пересчитывается при сдвиге за `O(1)`, а посимвольная проверка выполняется только при совпадении хешей. В среднем `O(n + m)`, в худшем — `O(n·m)`.

Полиномиальный хеш

h(s) = s₀·p^(m−1) + s₁·p^(m−2) + … + s_(m−1) (mod M). Сдвиг окна: вычесть вклад ушедшего символа, умножить на p, прибавить новый.

// mod < 2^30: произведения < 2^53, BigInt не нужен
const rabinKarp = (text, pat, base = 256, mod = 1_000_000_007) => {
  const n = text.length, m = pat.length;
  if (m === 0 || m > n) return [];
  const code = (s, i) => s.charCodeAt(i);
  let high = 1, hp = 0, hw = 0;
  for (let i = 0; i < m - 1; i++) high = (high * base) % mod;
  for (let i = 0; i < m; i++) {
    hp = (hp * base + code(pat, i)) % mod;
    hw = (hw * base + code(text, i)) % mod;
  }
  const res = [];
  for (let i = 0; i + m <= n; i++) {
    if (hw === hp && text.slice(i, i + m) === pat) res.push(i);
    if (i + m < n) {
      hw = ((hw - (code(text, i) * high) % mod + mod) * base + code(text, i + m)) % mod;
    }
  }
  return res;
};

Коллизии

• По парадоксу дней рождения при модуле ~10⁹ и 10⁵ хешах коллизии почти гарантированы, поэтому берут модуль 2⁶¹ − 1 (в JS — через BigInt) или двойное хеширование.
• Хеш по модулю 2⁶⁴ (через переполнение) ломается анти-тестом на строках Туэ–Морса при любом основании — нужен простой модуль, а основание лучше выбирать случайно.

Где сильнее KMP

• Поиск сразу множества образцов одной длины: хеши образцов в Set.
• Наибольшая повторяющаяся подстрока: бинпоиск по длине + хеши, O(n log n).
• Rolling hash в rsync и дедупликации.

Коротко для собеседования

Рабин–Карп пересчитывает хеш окна при сдвиге за O(1) и сравнивает строки только при совпадении хешей. Удобен для многих образцов и сравнения подстрок по префиксным хешам; от коллизий — большой модуль или два хеша.