Полиномиальное хеширование

Основной способ хешировать строки. Идея: смотреть на строку как на запись числа в системе счисления с основанием $p$.

Число $5348$ в десятичной записи — это $5 \cdot 10^3 + 3 \cdot 10^2 + 4 \cdot 10 + 8$. Сделаем то же самое со строкой:

$$h(s) = s_0 p^{n-1} + s_1 p^{n-2} + \dots + s_{n-1} p^0 \pmod m$$

где $s_i$ — числовой код $i$-го символа.

Без взятия по модулю такая запись однозначна: разным строкам соответствуют разные числа, как разным записям соответствуют разные числа в десятичной системе. Модуль сжимает бесконечное множество строк в конечный диапазон, и коллизии появляются — но уже не тривиальные.

Выбор параметров

Основание $p$ должно быть строго больше любого кода символа. Иначе система счисления «переполняется» и запись перестаёт быть однозначной: например, при $p = 2$ строки c (код 3) и aa (коды 1, 1) обе дают $3$.

Для строчных латинских букв берут что-нибудь от $31$ до $10^3$: 31, 131, 239, 257, 667. Конкретное значение не принципиально.

Модуль $m$ берут большим простым: $10^9+7$, $10^9+9$, $998244353$. Простота не обязательна теоретически, но избавляет от целого класса проблем и ничего не стоит.

Коды символов: начинайте с единицы

Самая коварная деталь всего раздела.

Естественно написать s[i] - 'a', чтобы a стало нулём. Так делать нельзя: тогда все строки, состоящие из одних a, получат хеш $0$ — и a, и aa, и aaa.

Это ровно тот «очевидный контрпример», которого быть не должно, и он найдётся на любом наборе тестов.

Правильно — s[i] - 'a' + 1, чтобы коды шли с единицы. Аналог: в записи числа не бывает ведущих нулей.

Вычисление: схема Горнера

Формулу выше не считают «в лоб» — возводить $p$ в степень для каждого символа незачем. Перепишем её со скобками:

$$h(s) = \Bigl(\bigl((s_0 \cdot p + s_1) \cdot p + s_2\bigr) \cdot p + \dots\Bigr) + s_{n-1}$$

Отсюда цикл:

long long h = 0;
for (char c : s) {
    h = mult(h, P);
    h = add(h, c - 'a' + 1);
}

Линия, одно умножение и одно сложение на символ. Функции add и mult — быстрая модульная арифметика; писать % напрямую не стоит.

По модулю нужно брать на каждом шаге. Накопить сумму и взять модуль в конце нельзя: long long переполнится, а остаток от переполненного значения — не тот остаток.

Проверка

На всех $9840$ строках длины от 1 до 8 над алфавитом из трёх букв полиномиальный хеш с $p = 667$, $m = 10^9+7$ даёт 9840 различных значений — ни одной коллизии.

Это не доказательство, но хороший признак: перебором маленьких строк контрпример не находится.

Отладка

Хеши — это большие бессмысленные числа, и смотреть на них глазами обычно бесполезно. Есть приём, который делает их читаемыми.

Возьмите на время отладки:

• алфавит из первых девяти букв, a…i, чтобы коды были от 1 до 9;
• основание $p = 10$;
• короткие строки, чтобы модуль не срабатывал.

Тогда строка abcea получит хеш $12351$ — то есть буквально свою запись цифрами. Любая ошибка в коде становится видна сразу: вместо ожидаемых цифр в хеше появляется что-то другое.

Приём стоит помнить: он превращает неотлаживаемую задачу в отлаживаемую за две минуты.

Что дальше

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