Полиномиальное хеширование строк: префиксные хеши, коллизии и двойной хеш
Полиномиальный хеш строки: префиксные хеши и сравнение подстрок за O(1), парадокс дней рождения и анти-хеш тесты, двойной хеш и модуль 2^61−1. Задачи и код на Python.
Коротко
| Операция | Сложность |
|---|---|
| Предподсчёт префиксных хешей | O(n) времени и памяти |
| Хеш любой подстроки | O(1) |
| Сравнение двух подстрок | O(1), с вероятностью ошибки |
| LCP двух суффиксов | O(log n) — бинарный поиск по длине |
- Строка превращается в многочлен, значение которого по модулю — её хеш.
- Префиксные хеши позволяют получить хеш любой подстроки вычитанием, как префиксные суммы.
- Равные строки всегда дают равные хеши, обратное верно лишь с высокой вероятностью. Вся инженерия хешей — про то, как сделать эту вероятность пренебрежимой.
Поиск образца в тексте скользящим хешем — отдельная тема, её мы разобрали в статье про алгоритм Рабина-Карпа. Здесь — о самом хеше как инструменте: как сравнивать произвольные подстроки, почему одного модуля часто мало и где хеши заменяют суффиксные структуры.
Зачем хешировать строки
Сравнение двух строк длины стоит . Пока сравнений мало, это не проблема. Но во многих задачах их квадратичное число:
- сколько различных подстрок в строке;
- какая самая длинная подстрока встречается дважды;
- является ли подстрока
s[l:r]палиндромом — и так для запросов; - отсортировать все суффиксы строки.
Если каждое сравнение подстрок стоит , такие задачи решаются на порядок быстрее. Хеширование даёт ровно это: строку произвольной длины мы заменяем числом и сравниваем числа.
Полиномиальный хеш
Строку рассматриваем как число в системе счисления с основанием :
Здесь — код символа, — основание, — модуль. Считается схемой Горнера за один проход:
def poly_hash(s: str, p: int = 31, mod: int = 10**9 + 7) -> int: h = 0 for ch in s: h = (h * p + ord(ch)) % mod return h print(poly_hash('abc')) # 96354 = 97·31² + 98·31 + 99
Почему именно многочлен, а не, скажем, сумма кодов? Сумма не учитывает порядок: у abc и cba она одинаковая. В многочлене каждая позиция получает свой «вес» , поэтому перестановка символов почти всегда меняет хеш.
Встречается и обратный порядок степеней: . Он тоже работает, но формула хеша подстроки получается неудобнее (нужно домножать на обратный элемент или выравнивать степени). Схема Горнера проще — ей и будем пользоваться.
Префиксные хеши и хеш подстроки за O(1)
Идея та же, что у префиксных сумм: заранее посчитаем хеши всех префиксов.
Хеш префикса длины «содержит» в себе префикс длины , сдвинутый на разрядов влево. Чтобы вырезать подстроку s[l:r], вычтем этот сдвинутый префикс:
Это прямой аналог десятичной арифметики: из числа 12345 вырезать «345» можно как .
class StringHash: def __init__(self, s: str, base: int = 911382323, mod: int = (1 << 61) - 1): self.mod = mod n = len(s) self.prefix = [0] * (n + 1) self.power = [1] * (n + 1) for i, ch in enumerate(s): self.prefix[i + 1] = (self.prefix[i] * base + ord(ch)) % mod self.power[i + 1] = self.power[i] * base % mod def get(self, l: int, r: int) -> int: """Хеш подстроки s[l:r] (r не включается).""" return (self.prefix[r] - self.prefix[l] * self.power[r - l]) % self.mod h = StringHash('abracadabra') print(h.get(0, 4) == h.get(7, 11)) # True: 'abra' == 'abra' print(h.get(0, 4) == h.get(1, 5)) # False: 'abra' != 'brac'
Обратите внимание на массив power: степени основания тоже предподсчитываются. Вызов pow(base, r - l, mod) на каждый запрос стоил бы .
Сравнивать хеши можно только у подстрок одинаковой длины. Для разных длин хеши несопоставимы — да и сами строки, очевидно, различны.
Коллизии: почему один хеш может подвести
Хеш сжимает бесконечное множество строк в значений, поэтому разные строки неизбежно иногда совпадают по хешу. Вопрос — насколько часто.
Слабые хеши ломаются сразу
Классический пример — String.hashCode() в Java. Это тот же полиномиальный хеш с основанием 31 и переполнением 32-битного числа. И у него есть коллизия из двух символов:
Склеивая блоки Aa и BB, можно получить строк длины с одинаковым хешем. Для хеш-таблицы в Java это лишь замедление (там равенство проверяется через equals), а вот в алгоритме, который доверяет хешу без проверки, — неправильный ответ.
Парадокс дней рождения
Допустим, хеш «идеально случайный» и модуль . Вероятность коллизии двух конкретных строк — около , то есть одна миллиардная. Кажется, бояться нечего.
Но в задачах мы обычно сравниваем не две строки, а множество: кладём хеши всех подстрок длины в set или сортируем их. Если строк , то пар — , и ожидаемое число коллизий:
Для и это около 5 коллизий, а вероятность хотя бы одной — примерно 99%. Это парадокс дней рождения: чтобы найти совпадение среди значений, достаточно порядка элементов. Для это всего ~30 тысяч строк.
Отсюда практическое правило: модуль должен быть заметно больше квадрата числа сравниваемых хешей. Для – строк нужен модуль порядка и больше.
Анти-хеш тесты и переполнение 2^64
Соблазнительно не брать модуль вовсе, а позволить 64-битному числу переполняться: это быстро, и «модуль» огромен. Но модуль-степень двойки ломается целенаправленно.
Строка Туэ–Морса строится так: начинаем с a, затем каждый раз приписываем к строке её же копию с заменой a ↔ b. После 11 итераций получаем строку длины 2048. Её «инверсия» (все a заменены на b и наоборот) — другая строка, но хеши по модулю совпадают для любого нечётного основания:
def thue_morse(k: int) -> str: s = 'a' for _ in range(k): s += ''.join('b' if c == 'a' else 'a' for c in s) return s def hash64(s: str, base: int) -> int: h = 0 for ch in s: h = (h * base + ord(ch)) & ((1 << 64) - 1) # переполнение uint64 return h a = thue_morse(11) b = ''.join('b' if c == 'a' else 'a' for c in a) print(a != b, all(hash64(a, p) == hash64(b, p) for p in [31, 131, 911382323]))
True True
Для чётного основания всё ещё проще: старшие символы «выдвигаются» за 64 бита, и хеш зависит только от последних 64 символов. На олимпиадах и в задачах с открытыми тестами такие строки встречаются специально. Вывод: **модуль — большое простое число**, не степень двойки.
## Как выбрать параметры
**Основание $p$** — больше размера алфавита, иначе разные символы «сольются». Для строчных латинских букв хватит 31, для произвольных символов берут большое число.
Ещё надёжнее — **случайное основание**, выбранное при запуске программы:
```python
import random
base = random.randrange(256, (1 << 61) - 1)
Для фиксированных строк вероятность коллизии при случайном оценивается сверху как (многочлен степени имеет не больше корней по модулю простого ). Главное — злоумышленник не знает заранее и не может подобрать тест.
Модуль — большое простое. Популярные варианты:
| Модуль | Плюсы | Минусы |
|---|---|---|
| помещается в int, произведение — в int64 | для строк коллизии почти гарантированы | |
| два модуля | итоговое пространство | вдвое больше вычислений и памяти |
| одно число, пространство | в C++ нужно __int128 или трюк с битовыми сдвигами | |
| (переполнение) | самый быстрый | ломается строкой Туэ–Морса |
В Python целые числа неограниченные, поэтому модуль работает «из коробки» — именно его мы взяли в классе StringHash. В C++ и Java произведение двух 61-битных чисел не влезает в 64 бита, нужна 128-битная арифметика или специальная реализация умножения.
Двойной хеш
Если язык или привычка требуют модулей около , считают два независимых хеша с разными модулями (и желательно разными основаниями) и сравнивают пары:
class DoubleHash: def __init__(self, s: str): self.h1 = StringHash(s, base=131, mod=10**9 + 7) self.h2 = StringHash(s, base=137, mod=10**9 + 9) def get(self, l: int, r: int) -> tuple[int, int]: return self.h1.get(l, r), self.h2.get(l, r)
Две строки считаются равными, только если совпали оба хеша. Пространство значений фактически становится , и парадокс дней рождения срабатывает только для миллиарда строк.
Пары удобно класть в set и dict как кортежи. В C++ и Java их часто склеивают в одно 64-битное число: h1 * M2 + h2 или (h1 << 32) | h2.
Сравнение подстрок: LCP и лексикографический порядок
Равенство подстрок за — это только начало. Вместе с бинарным поиском хеши дают длину наибольшего общего префикса (LCP) любых двух суффиксов за .
Идея: если префиксы длины совпадают, то совпадают и все более короткие. Значит, «совпадают ли префиксы длины » — монотонный предикат, и максимальное ищется бинарным поиском по ответу.
def lcp(h: StringHash, i: int, j: int, n: int) -> int: """Длина общего префикса суффиксов s[i:] и s[j:].""" lo, hi = 0, n - max(i, j) while lo < hi: mid = (lo + hi + 1) // 2 if h.get(i, i + mid) == h.get(j, j + mid): lo = mid else: hi = mid - 1 return lo s = 'abracadabra' h = StringHash(s) print(lcp(h, 0, 7, len(s))) # 4: 'abra' print(lcp(h, 0, 3, len(s))) # 1: 'a'
Зная LCP, сравнить подстроки лексикографически просто: посмотреть на первый несовпадающий символ.
from functools import cmp_to_key def compare(s: str, h: StringHash, i: int, j: int) -> int: """Сравнивает суффиксы s[i:] и s[j:]: -1, 0 или 1.""" n = len(s) k = lcp(h, i, j, n) if i + k == n or j + k == n: # один суффикс — префикс другого return (n - i > n - j) - (n - i < n - j) return -1 if s[i + k] < s[j + k] else 1 s = 'banana' h = StringHash(s) print(sorted(range(len(s)), key=cmp_to_key(lambda i, j: compare(s, h, i, j)))) # [5, 3, 1, 0, 4, 2]
Это суффиксный массив за в несколько строк. Специализированные алгоритмы из статьи про суффиксный массив быстрее, но вариант с хешами пишется на собеседовании за пять минут и почти не содержит мест для ошибки.
Типовые задачи
Количество различных подстрок
Для каждой длины положим хеши всех подстрок в множество:
def count_distinct_substrings(s: str) -> int: h = StringHash(s) n = len(s) total = 0 for length in range(1, n + 1): total += len({h.get(i, i + length) for i in range(n - length + 1)}) return total print(count_distinct_substrings('abab')) # 7: a, b, ab, ba, aba, bab, abab
Время вместо при сравнении строк напрямую. Здесь хорошо видно, почему нужен большой модуль: подстрок порядка , и при это уже 12,5 миллиона хешей.
Самая длинная повторяющаяся подстрока
LeetCode 1044 «Longest Duplicate Substring» — задача уровня hard, которая решается бинарным поиском по длине и хешами. Если повтор длины есть, то есть и повтор длины (отрежем последний символ), так что предикат монотонный.
def longest_dup_substring(s: str) -> str: h = StringHash(s) n = len(s) def find(length: int) -> int: """Начало повторяющейся подстроки длины length или -1.""" seen = {} for i in range(n - length + 1): key = h.get(i, i + length) if key in seen and s[seen[key]:seen[key] + length] == s[i:i + length]: return i seen.setdefault(key, i) return -1 lo, hi, best, start = 1, n - 1, 0, -1 while lo <= hi: mid = (lo + hi) // 2 pos = find(mid) if pos != -1: best, start = mid, pos lo = mid + 1 else: hi = mid - 1 return s[start:start + best] if best else '' print(longest_dup_substring('banana')) # ana
Итог — . Посимвольная проверка при совпадении хешей страхует от ложного ответа. Её стоимость платится, только когда кандидат найден, после чего функция сразу возвращается, — асимптотику она не портит.
Та же схема находит наибольшую общую подстроку двух строк: для фиксированной длины кладём хеши подстрок первой строки в множество и ищем совпадения среди подстрок второй.
Палиндром ли подстрока
Подстрока — палиндром, если она равна своему развороту. Построим хеши для строки и для её разворота: подстроке s[l:r] в развёрнутой строке соответствует отрезок [n - r, n - l).
class PalindromeChecker: def __init__(self, s: str): self.n = len(s) self.fwd = StringHash(s) self.rev = StringHash(s[::-1]) def is_palindrome(self, l: int, r: int) -> bool: """Является ли s[l:r] палиндромом.""" return self.fwd.get(l, r) == self.rev.get(self.n - r, self.n - l) pc = PalindromeChecker('abacaba') print(pc.is_palindrome(0, 7), pc.is_palindrome(0, 3), pc.is_palindrome(1, 4)) # True True False
Каждый запрос — . Для одной строки целиком это избыточно (хватит двух указателей), но когда запросов много, хеши выигрывают. Плюс бинарный поиск по радиусу даёт длиннейший палиндром за — проще в написании, чем алгоритм Манакера, хотя и медленнее.
Общий префикс нескольких строк
Задача Longest Common Prefix решается и без хешей — посимвольным сравнением за , где — суммарная длина. Но вариант с хешами полезен как упражнение: бинарный поиск по длине, на каждом шаге сравниваем хеши префиксов.
def longest_common_prefix(strs: list[str]) -> str: shortest = min(strs, key=len) hashes = [StringHash(s) for s in strs] def ok(length: int) -> bool: target = hashes[0].get(0, length) return all(h.get(0, length) == target for h in hashes) lo, hi = 0, len(shortest) while lo < hi: mid = (lo + hi + 1) // 2 if ok(mid): lo = mid else: hi = mid - 1 return shortest[:lo] print(longest_common_prefix(['flower', 'flow', 'flight'])) # fl
На собеседовании такое решение — перебор, но вопрос «а если строки приходят потоком и запросов LCP много?» как раз ведёт к хешам.
Хеши против детерминированных алгоритмов
| Задача | Хеши | Детерминированно |
|---|---|---|
| Поиск образца | Рабин-Карп | КМП, Z-функция |
| Сравнение подстрок, LCP | / | суффиксный массив + LCP + sparse table |
| Различные подстроки | суффиксный автомат, | |
| Палиндромы | Манакер, |
Детерминированные алгоритмы быстрее и не ошибаются, но каждый из них — отдельная сложная конструкция. Хеши — один универсальный инструмент на 15 строк, который закрывает все строки таблицы. Это и есть их главная ценность: когда точного алгоритма не помните или его долго писать, хеш почти всегда спасает.
Типичные ошибки
Маленький модуль при большом числе сравнений. Модуль и хешей в одном множестве — почти гарантированная коллизия. Используйте или двойной хеш.
Переполнение вместо модуля. Хеш по модулю ломается специально построенным тестом. Беззнаковое переполнение — это не «бесплатный модуль».
Отрицательный остаток. В C++, Java и JavaScript (a - b) % M может быть отрицательным. Пишите ((a - b) % M + M) % M. В Python оператор % всегда возвращает неотрицательное значение.
Код символа 0. Если кодировать 'a' как 0, то a, aa и aaa получат хеш 0, а b и ab — одинаковый хеш 1. Пока сравниваются подстроки одной длины, это безвредно, но стоит сложить хеши разных длин в одно множество — и ответ неверный. Используйте ord(ch) или ord(ch) - ord('a') + 1.
Основание меньше алфавита. При и кодах символов до 122 разные строки начинают «переносить разряды» и совпадать.
Переполнение в JavaScript. Числа в JS — double, точная целочисленная арифметика заканчивается на . Произведение двух чисел около уже теряет точность. Берите BigInt или модуль поменьше с двойным хешем, следя, чтобы произведение не превышало .
pow на каждый запрос. Степени основания предподсчитываются один раз — иначе превращается в .
Где встречается на собеседованиях
Напрямую «напишите полиномиальный хеш» спрашивают редко. Хеш появляется как оптимизация:
- Repeated DNA Sequences (LeetCode 187) — повторяющиеся подстроки фиксированной длины 10;
- Longest Duplicate Substring (LeetCode 1044) — бинарный поиск плюс хеши;
- Distinct Echo Substrings (LeetCode 1316) — подстроки вида
aa, проверка половин за ; - Shortest Palindrome (LeetCode 214) — самый длинный префикс-палиндром через прямой и обратный хеш;
- вопросы про дедупликацию документов, сравнение файлов и контрольные суммы в system design.
Хороший ответ включает три вещи: формулу хеша подстроки, оценку вероятности коллизии через парадокс дней рождения и способ защиты — большой модуль, двойной хеш или проверку совпадения напрямую.
Что запомнить
- Полиномиальный хеш — строка как число в системе с основанием по модулю .
- Префиксные хеши и предподсчитанные степени дают хеш любой подстроки за : .
- Вероятность коллизии растёт как , а не . Для строк модуль недостаточен.
- Надёжные варианты — модуль , двойной хеш, случайное основание. Ненадёжный — переполнение .
- Хеш + бинарный поиск по длине решает LCP, длиннейший повтор, длиннейший палиндром и сравнение строк.
- Если цена ошибки высока, проверяйте найденное совпадение посимвольно.