«Хорошая» хеш-функция:

Обычно хеш-функция не является взаимно однозначной: одному хешу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хешами, чем с самими объектами. Пусть даны $n$строк длины $m$, и нас просят $q$ раз проверять произвольные две на равенство. Вместо наивной проверки за O($q \cdot n \cdot m$), мы можем посчитать хеши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Хешируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

В этом разделе мы в основном сфокусируемся на строках.

Будем считать, что строка — это последовательность чисел от 1 до $m$ (размер алфавита). В C/C++ тип charэто на самом деле тоже число (8-битное), поэтому можно вычитать из символов минимальный код и кастовать в число:

Определим прямой полиномиальный хеш строки как значение следующего многочлена:

$h_f​=(s_0​+s_1​k+s_2​k^2+…+s_n​k^n)\mod p$

Здесь $k$ — произвольное число больше размера алфавита, а $p$ — достаточно большой модуль (вообще говоря, не обязательно простой).

Его можно посчитать за линейное время, поддерживая переменную, равную $k$ в нужной степени:

Можем ещё определить обратный полиномиальный хеш:

$h_b = (s_0 k^n + s_1 k^{n-1} + \ldots + s_n) \mod p$

Его преимущество в том, что можно писать на одну строчку кода меньше:

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хеш и обозначать его просто буквой $h$.

Используя тот факт, что хеш — это значение многочлена, можно быстро пересчитывать хеш от результата выполнения многих строковых операций.

Например, если нужно посчитать хеш от конкатенации строк $a$ и $b$ (строку $b$ приписали в конец строки $a$), то можно просто хеш $b$ домножить на $k^{|a|}$ и сложить с хешом $a$:

$h(ab) = h(a) + k^{|a|} \cdot h(b)$

Удалить префикс строки можно так:

$h(b) = \frac{h(ab) - h(a)}{k^{|a|}}$

А суффикс — ещё проще:

$h(a) = h(ab) - k^{|a|} \cdot h(b)$

В задачах нам часто понадобится домножать $k$ в какой-то степени, поэтому имеет смысл предподсчитать все нужные степени и сохранить в массиве:

Как это использовать в реальных задачах? Пусть нам надо отвечать на запросы проверки на равенство произвольных подстрок одной большой строки. Подсчитаем значение хеш-функции для каждого префикса:

Теперь с помощью этих префиксных хешей мы можем определить функцию, которая будет считать хеш на произвольном подотрезке:

$h(s[l:r]) = \frac{h_r-h_l}{k^l}$

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хеш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к $n$-ной.

$\hat{h}(s[l:r]) = k^{n-l} (h_r-h_l)$

Так проще — теперь нужно домножать, а не делить:

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за $O(1)$.

Упражнение. Напишите то же самое, но используя обратный полиномиальный хеш — этот способ тоже имеет право на существование, и местами он даже проще. Обратный хеш подстроки принято считать и использовать в стандартном виде из определения, поскольку там нет необходимости в делении.

Лайфхак. Если взять обратный полиномиальный хеш короткой строки на небольшом алфавите с $k=10$, то числовое значение хеша строки будет наглядно соотноситься с самой строкой:

$h(abacaba)=1213121$

Этим удобно пользоваться при дебаге.

Количество разных подстрок. Посчитаем хеши от всех подстрок за $O(n^2)$ и добавим их все в std::set. Чтобы получить ответ, просто вызовем set.size().

Поиск подстроки в строке. Можно посчитать хеши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хеш текущей подстроки. Если хеш какой-то из этих подстрок совпал с хешом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение подстрок на больше-меньше, а не только на равенство. У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше в обеих подстроках возьмём идущий за ним символ и сравним. Это будет работать за $O(\log n)$.

Палиндромность подстроки. Можно посчитать два массива — обратные хеши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно. Это будет работать за $O(n \log n)$, хотя это можно решить и линейно.

У алгоритмов, использующих хеширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хеширование — можно в оффлайне сгенерировать тест против конкретного решения. Есть даже гайды про то, как это делать.

Событие, когда два хеша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set $O(n^2)$ различных случайных значений в промежутке $[0, m)$. Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать $m$, чтобы не бояться такого?

Практическое правило: если вам нужно хранить $n$ различных хешей, то безопасный модуль — это число порядка $10 \cdot n^2$. Обоснование — см. парадокс дней рождений.

Не всегда такой модуль можно выбрать один — если он будет слишком большой, то при умножении будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хешей параллельно.

Можно также брать «модуль» $2^{64}$. У него есть несколько преимуществ:

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако его добавляют далеко не на все контесты — имейте это в виду.

В выборе же $k$ ограничения не такие серьезные:

Главное — чтобы значения $k$ и модуля не знал человек, который генерирует тесты.

Более общее утверждение: в мультимножество нужно добавить $\Theta(\sqrt{n})$ случайных чисел от 1 до $n$, чтобы какие-то два совпали.