Построение хеш-функций для строк

Гоша: Как вычислять хеш-функцию для целых чисел — ясно. А как вычислять хеш-функцию для строк?

Тимофей: Существует метод, который называется полиномиальный хеш, где хеш строки $s$ длины $n$ вычисляются по формуле:

$h_{2}(s)=\left(s_{0} a^{n-1}+s_{1} a^{n-2}+\cdots+s_{n-2} a+s_{n-1}\right) \bmod m$.

Где $s_0, s_1, ..., s_{n-1}$ — коды символов (например, ASCII-коды), а $m$ и $a$ — выбранные константы.

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

Хотим, чтобы все значения $s \cdot a \bmod m, 0 \leqslant s < m$ были различными. На самом деле для этого достаточно, чтобы $a$ и $m$ были взаимно простыми.

Обычно в качестве $a$ берут какое-то простое число.

Для избежания коллизий, если строки короткие, лучше выбирать $a$ побольше. Иначе значения будут скапливаться в начале массива. Если строки длинные, выбор величины $a$ не так важен. В этом случае в сумму будут входить значения $a$ в достаточно больших степенях.

Алла: А можешь привести пример?

Тимофей: Вычислим хеш от строки “ABACB”. ASCII-коды символов “A”, “B” и “C” равны 65, 66 и 67.

В качестве констант возьмём: $a=3$, а $m=97$.

Тогда значение хеш-функции вычисляется так:

Полиномиальный хеш можно вычислить эффективно с использованием метода Горнера:

Может воспользуемся методом Горнера для нашего примера:

Тимофей: При использовании полиномиального хеширования значение хеш-функции любой строки можно вычислить за константное время. Для этого нужно сделать предобработку, которая занимает $O(n)$. Про этот метод вы узнаете немного позже, когда я буду рассказывать про специальные алгоритмы работы со строками.

Алла: А расскажешь про свойства, которыми должна обладать хорошая хеш-функция?

Тимофей: Да, конечно. Скоро всё узнаете.

Решите задачи C, I, L: https://contest.yandex.ru/contest/19095/problems/