Полиномиальное хеширование строк
Содержание
Зачем нужны хеши?
Сравнивать строки $S_1, S_2$ мы умеем за $O(|S|)$. Если бы мы могли для каждой из строк за $O(1)$ вычислить какую-нибудь функцию, которая для разных аргументов принимает разные значения (такие функции называются инъекциями), то мы могли бы сравнивать строки уже за $O(1)$.
Хеш-функцией назовём любую функцию, которая отображает строки (на самом деле не только их) в ${0, 1, \dots, M}$ для некоторого постоянного $M$. Хэшем строки будем называть значение хеш-функции на ней.
По принципу Дирихле, если количество различных строк, которые наша функция может принимать, превышает $M$, то найдутся две строки с одинаковыми хешами $\implies$ наша хеш-функция $~-$ не инъекция $\implies$ значение $M$ стоит выбирать как можно больше.
Полиномиальный хеш
Положим $h(s_0s_2...s_n) = (p^{n+1}s_0 + p^{n}s_1 + \dots + p^1s_{n-1} + s_n) \mod M$, где $p, M ~-$ некоторые фиксированные константы, требования к которым мы предъявим чуть позже.
Теперь давайте с помощью такого хеша научимся решать задачи.
Предподсчёт
Вспомним, что мы хотели считать хеш строки за $O(1)$, значит, чтобы быстро сравнивать строки на равенство, надо сделать какой-то предподсчёт.
Давайте насчитаем хеш всех префиксов строки: $$ h[i] = h(s_0s_1 \dots s_{i-1}) $$ Положим $h[0] = 0$, таким образом в $h[i]$ хранится хеш префикса до $i$-го символа невключительно (чтобы не обрабатывать отдельно случай, когда мы захотим посчитать хеш на префиксе).
Чтобы предподсчитать все хеши за $O(|S|)$, а не за $O(|S|^2)$, заметим что $h[i+1] = (h[i] \times p + s[i]) \mod M$.
Находим хеши подстрок
Теперь заметим, что $h(s_Ls_{L+1} \dots s_{R-1}) = p^{R-L-1}s_L + p^{R-L-2}s_{L+1} + \dots + p^{1}s_{R-2} + s_{R-1}$. Из хешей на префиксах мы знаем:
$$ h[R] = h(s_0 \dots s_{R-1}) = p^{R-1}s_0 + \dots + p^{R-L}s_{L-1} + \underbrace{p^{R-L-1}s_L + \dots + s_{R-1}}_{h(s_Ls_{L+1} \dots s_{R-1})} \\ h[L] = h(s_0 \dots s_{L-1}) = p^{L-1}s_0 + \dots + s_{L-1} $$
Если вторую строчку умножить на $p^{R-L}$ (по модулю M) и вычесть из первой (тоже по модулю M), то мы получим $h(s_L \dots s_{R-1})$, а это в точности то, что мы искали.
Какие $p$ и $M$ выбрать?
Первое требование $~-$ на $p$: $p > max \{s_i\}$. Если это так, то хеш от строки без взятия по модулю (по сути, значение многочлена в некоторой точке $~-$ отсюда и название полиномиальное хеширование) $~-$ инъекция. А вот если брать $p$ меньше, чем $max \{s_i\}$, то коллизии могут появиться ещё на этапе подсчёта.
Далее, мы хотим выбрать такие $p$ и $M$, чтобы минимизировать вероятность коллизии. В частности, мы хотим минимизировать количество таких остатков, которые не могут быть хешом никакой строки. Давайте тогда возьмём взаимнопростые $p$ и $M$.
Как взломать полиномиальное хеширование по модулю $2^{64}$?
Что делать, если задача не заходит?
Из парадокса дней рождений следует, что если объектов хотя бы корень от числа возможных значений хеш-функции, то коллизия будет с достаточно большой вероятностью. В этом случае, можно
- Использовать хеширование по 2 разным парам $(p, M)$
- Воспользоваться хеш-таблицами:
Готовый код для вашего олимпиадного шаблона by Серёжа Копелиович aka burunduk1
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex