Добрый день.

Это пост о мелочах в реализации хешей.

Сегодня ребята гуглили "как писать полиномиальные хеши", но нагулили лишь две ссылки на тему "как не надо писать полиномиальные хеши" — e-maxx и habr.

А можно писать иначе — short и full. Последняя версия устойчива к антихеш тестам, её можно копипастить.

Теперь подробно. Есть два способа. Оба для краткости будут написаны по модулю 2⁶⁴, то есть падают на строке Туе-Морса.

Общая часть:

const int P = 239017; // Если брать простой модуль, здесь стоит писать rand()!
// s - строка, n - её длина

Первый способ (я пишу так):

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {0, s[0], s[0]*P + s[1], s[0]*P^2 + s[1]*P + s[2], ...}
unsigned long long h[n + 1], deg[n + 1];
h[0] = 0, deg[0] = 1;
for (int i = 0; i < n; i++) {
  h[i + 1] = h[i] * P + s[i];
  deg[i + 1] = deg[i] * P;
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  return h[r + 1] - h[l] * deg[r - l + 1];
};

Второй способ:

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {s[0], s[0] + s[1]*P, s[0] + s[1]*P + s[2]*P^2, ...}
unsigned long long h[n], deg[n];
h[0] = s[0], deg[0] = 1;
for (int i = 1; i < n; i++) {
  deg[i] = deg[i - 1] * P;
  h[i] = h[i - 1] + s[i] * deg[i];
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  if (l == 0)
    return h[r];
  return h[r] - h[l - 1];
};

Отличия здесь два

Направление s₀P^n - 1 + s₁P^n - 2 + ... + s_n - 1 или s₀ + s₁P + s₂P² + ... + s_n - 1P^n - 1?

В первом способе, чтобы сравнить две строки [l1..r1] и [l2..r2], достаточно написать get_hash(l1, r1) == get_hash(l2, r2). То есть, функция get_hash честно возвращает хеш. Можно, например, найти количество различных подстрок, положив все хеши в хеш-таблицу.

Во втором случае функция get_hash на самом деле возвращает не хеш, а хеш, домноженный на некоторую степень P, поэтому придётся писать так deg[r2] * get_hash(l1, r1) == deg[r1] * get_hash(l2, r2) (на e-maxx правда чуть страшнее). А использовать хеши иначе не получится. Можно модифицировать функцию get_hash, использовать честный хеш true_hash(l, r) = deg[n - r - 1] * get_hash(l, r), но у такого способа есть минус — мы предполагаем, что знаем максимальную длину строки. Это не всегда удобно, а при онлайн-решениях иногда и не правда.

У второго способа ещё есть вариация с делением по модулю. Так писать точно не нужно.

С чего начинать массив h? С 0 или с s[0]?

Если мы начинаем с 0, мы получаем более короткий и быстрый код (да, да, чтобы if-у выполниться, нужно время!). Оценивая скорость, заметьте, что умножений будет столько же.

Если же мы начинаем в s[0], то получаем массив длины n, то есть экономим O(1) памяти.

Как лучше, решайте сами. Я всем рекламирую первый вариант. Если есть конструктивные замечания или альтернативные версии, буду рад услышать.

Выбор простого модуля

Отдельный привет всем, кто говорит "число P можно выбирать любым". P должно быть больше размера алфавита. Если это так, то хеш, вычисленный без взятия по модулю, как длинное число, инъективен. Иначе уже на этапе вычисления без модуля могут быть коллизии. Примеры, как нельзя делать: алфавит "a..z", P = 13, алфавит ASCII 33..127, P = 31.

P.S. Кстати, как правильно пишется "хеш", или "хэш"? Моя версия — "хеш".

UPD: Подсказывают, что, если писать без unsigned, получится Undefined Behaviour. Спасибо Лёше Левину.

UPD: Чтобы хеш точно нельзя было сломать, можно точку P выбирать как max(Σ, rand()). Версия full пропатчилась. Спасибо Kaban-5, nk.karpov.