Полиномиальное хеширование строк
Содержание
Зачем нужны хеши?
Сравнивать строки $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}$. Из хешей на префиксах мы знаем: '"`UNIQ-MathJax3-QINU`"' Если вторую строчку умножить на $p^{R-L}$ '''(по модулю M)''' и вычесть из первой (тоже по модулю M), то мы получим $h(s_L \dots s_{R-1})$, а это в точности то, что мы искали. =='"`UNIQ--h-3--QINU`"' Какие $p$ и $M$ выбрать? == Первое требование (б/д) $~-$ на $p$: $p > max \{s_i\}$. Если это так, то хеш от строки без взятия по модулю (по сути, значение многочлена в некоторой точке $~-$ отсюда и название ''полиномиальное хеширование'') $~-$ инъекция. А вот если брать $p$ меньше, чем $max \{s_i\}$, то коллизии могут появиться ещё на этапе подсчёта. Далее, мы хотим выбрать такие $p$ и $M$, чтобы минимизировать вероятность коллизии. В частности, мы хотим минимизировать количество таких остатков, которые не могут быть хешом никакой строки. Давайте тогда возьмём взаимнопростые $p$ и $M$. =='"`UNIQ--h-4--QINU`"' [https://codeforces.com/blog/entry/4898?locale=ru Как взломать полиномиальное хеширование по модулю $2^{64}$?] == Что делать с коллизиями? Из [[Парадокс дней рождений#Общая формулировка|парадокса дней рождений]] следует, что если объектов хотя бы корень от числа возможных значений хеш-функции, то коллизия будет с достаточно большой вероятностью. В этом случае, можно # Использовать хеширование по 2 разным парам $(p, M)$
- Воспользоваться хеш-таблицами:
Готовый код для вашего олимпиадного шаблона by Серёжа Копелиович aka burunduk1
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex