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

Часто требуется проверить, равны ли две подстроки. Посимвольное сравнение медленно, поэтому мы превращаем каждую строку в число. 🔢

Хеш отображает строку в одно целое число. Если строки различаются, их хеши почти всегда тоже различаются.

Мы воспринимаем каждый символ как цифру в системе с основанием p. Такой многочленный взгляд превращает строку в одну большую взвешенную сумму.

Выберите простое основание, например 31, и большое простое число в качестве модуля. Взятие по модулю сохраняет числа небольшими и предотвращает переполнение.

Пройдите по строке и добавляйте каждый символ по схеме Горнера, выполняя взятие по модулю на каждом шаге.

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

Также предварительно вычислите степени основания. Они выравнивают два префикса при вычитании.

Хеш s[l..r] получают вычитанием двух префиксных хешей с поправкой на степень основания. Постоянное время на каждый запрос.

Две разные строки могут иметь один и тот же хеш — это коллизия. Такое случается редко, но на соревнованиях иногда специально подбирают входные данные, чтобы её вызвать.

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

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

Выберите подходящий инструмент для безопасного сравнения множества подстрок.

Теперь Вы умеете превращать строки в полиномиальные хеши, получать хеш любой подстроки за O(1) и защищаться от коллизий. 🚀