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

Полиномиальный хеш строки: префиксные хеши и сравнение подстрок за O(1), парадокс дней рождения и анти-хеш тесты, двойной хеш и модуль 2^61−1. Задачи и код на Python.

16 мин чтенияалгоритмы · строки · хеширование · python

Коротко

ОперацияСложность
Предподсчёт префиксных хешейO(n) времени и памяти
Хеш любой подстрокиO(1)
Сравнение двух подстрокO(1), с вероятностью ошибки
LCP двух суффиксовO(log n) — бинарный поиск по длине
  • Строка превращается в многочлен, значение которого по модулю — её хеш.
  • Префиксные хеши позволяют получить хеш любой подстроки вычитанием, как префиксные суммы.
  • Равные строки всегда дают равные хеши, обратное верно лишь с высокой вероятностью. Вся инженерия хешей — про то, как сделать эту вероятность пренебрежимой.

Поиск образца в тексте скользящим хешем — отдельная тема, её мы разобрали в статье про алгоритм Рабина-Карпа. Здесь — о самом хеше как инструменте: как сравнивать произвольные подстроки, почему одного модуля 109+710^9+7 часто мало и где хеши заменяют суффиксные структуры.

Зачем хешировать строки

Сравнение двух строк длины mm стоит O(m)O(m). Пока сравнений мало, это не проблема. Но во многих задачах их квадратичное число:

  • сколько различных подстрок в строке;
  • какая самая длинная подстрока встречается дважды;
  • является ли подстрока s[l:r] палиндромом — и так для 10510^5 запросов;
  • отсортировать все суффиксы строки.

Если каждое сравнение подстрок стоит O(1)O(1), такие задачи решаются на порядок быстрее. Хеширование даёт ровно это: строку произвольной длины мы заменяем числом и сравниваем числа.

Полиномиальный хеш

Строку s=s0s1…sn−1s = s_0 s_1 \dots s_{n-1} рассматриваем как число в системе счисления с основанием pp:

h(s)=(s0⋅pn−1+s1⋅pn−2+⋯+sn−1⋅p0) mod Mh(s) = \left(s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \dots + s_{n-1} \cdot p^0\right) \bmod M

Здесь sis_i — код символа, pp — основание, MM — модуль. Считается схемой Горнера за один проход:

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 она одинаковая. В многочлене каждая позиция получает свой «вес» pkp^k, поэтому перестановка символов почти всегда меняет хеш.

Встречается и обратный порядок степеней: s0⋅p0+s1⋅p1+…s_0 \cdot p^0 + s_1 \cdot p^1 + \dots. Он тоже работает, но формула хеша подстроки получается неудобнее (нужно домножать на обратный элемент или выравнивать степени). Схема Горнера проще — ей и будем пользоваться.

Префиксные хеши и хеш подстроки за O(1)

Идея та же, что у префиксных сумм: заранее посчитаем хеши всех префиксов.

H[0]=0,H[i+1]=H[i]⋅p+si(modM)H[0] = 0, \qquad H[i+1] = H[i] \cdot p + s_i \pmod M

Хеш префикса длины rr «содержит» в себе префикс длины ll, сдвинутый на r−lr - l разрядов влево. Чтобы вырезать подстроку s[l:r], вычтем этот сдвинутый префикс:

h(s[l:r])=H[r]−H[l]⋅p r−l(modM)h(s[l:r]) = H[r] - H[l] \cdot p^{\,r-l} \pmod M

Это прямой аналог десятичной арифметики: из числа 12345 вырезать «345» можно как 12345−12⋅10312345 - 12 \cdot 10^3.

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) на каждый запрос стоил бы O(log⁡n)O(\log n).

Сравнивать хеши можно только у подстрок одинаковой длины. Для разных длин хеши несопоставимы — да и сами строки, очевидно, различны.

Коллизии: почему один хеш может подвести

Хеш сжимает бесконечное множество строк в MM значений, поэтому разные строки неизбежно иногда совпадают по хешу. Вопрос — насколько часто.

Слабые хеши ломаются сразу

Классический пример — String.hashCode() в Java. Это тот же полиномиальный хеш с основанием 31 и переполнением 32-битного числа. И у него есть коллизия из двух символов:

h(Aa)=65⋅31+97=2112,h(BB)=66⋅31+66=2112h(\texttt{Aa}) = 65 \cdot 31 + 97 = 2112, \qquad h(\texttt{BB}) = 66 \cdot 31 + 66 = 2112

Склеивая блоки Aa и BB, можно получить 2k2^k строк длины 2k2k с одинаковым хешем. Для хеш-таблицы в Java это лишь замедление (там равенство проверяется через equals), а вот в алгоритме, который доверяет хешу без проверки, — неправильный ответ.

Парадокс дней рождения

Допустим, хеш «идеально случайный» и модуль M=109+7M = 10^9 + 7. Вероятность коллизии двух конкретных строк — около 1/M1/M, то есть одна миллиардная. Кажется, бояться нечего.

Но в задачах мы обычно сравниваем не две строки, а множество: кладём хеши всех подстрок длины kk в set или сортируем их. Если строк NN, то пар — N(N−1)/2N(N-1)/2, и ожидаемое число коллизий:

N(N−1)2M\frac{N(N-1)}{2M}

Для N=105N = 10^5 и M≈109M \approx 10^9 это около 5 коллизий, а вероятность хотя бы одной — примерно 99%. Это парадокс дней рождения: чтобы найти совпадение среди MM значений, достаточно порядка M\sqrt{M} элементов. Для M=109M = 10^9 это всего ~30 тысяч строк.

Отсюда практическое правило: модуль должен быть заметно больше квадрата числа сравниваемых хешей. Для 10510^5–10610^6 строк нужен модуль порядка 101810^{18} и больше.

Анти-хеш тесты и переполнение 2^64

Соблазнительно не брать модуль вовсе, а позволить 64-битному числу переполняться: это быстро, и «модуль» 2642^{64} огромен. Но модуль-степень двойки ломается целенаправленно.

Строка Туэ–Морса строится так: начинаем с a, затем каждый раз приписываем к строке её же копию с заменой a ↔ b. После 11 итераций получаем строку длины 2048. Её «инверсия» (все a заменены на b и наоборот) — другая строка, но хеши по модулю 2642^{64} совпадают для любого нечётного основания:

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)

Для фиксированных строк вероятность коллизии при случайном pp оценивается сверху как n/Mn / M (многочлен степени nn имеет не больше nn корней по модулю простого MM). Главное — злоумышленник не знает pp заранее и не может подобрать тест.

Модуль MM — большое простое. Популярные варианты:

МодульПлюсыМинусы
109+710^9 + 7помещается в int, произведение — в int64для 10510^5 строк коллизии почти гарантированы
два модуля ≈109\approx 10^9итоговое пространство ≈1018\approx 10^{18}вдвое больше вычислений и памяти
261−12^{61} - 1одно число, пространство ≈2.3⋅1018\approx 2.3 \cdot 10^{18}в C++ нужно __int128 или трюк с битовыми сдвигами
2642^{64} (переполнение)самый быстрыйломается строкой Туэ–Морса

В Python целые числа неограниченные, поэтому модуль 261−12^{61} - 1 работает «из коробки» — именно его мы взяли в классе StringHash. В C++ и Java произведение двух 61-битных чисел не влезает в 64 бита, нужна 128-битная арифметика или специальная реализация умножения.

Двойной хеш

Если язык или привычка требуют модулей около 10910^9, считают два независимых хеша с разными модулями (и желательно разными основаниями) и сравнивают пары:

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)

Две строки считаются равными, только если совпали оба хеша. Пространство значений фактически становится M1⋅M2≈1018M_1 \cdot M_2 \approx 10^{18}, и парадокс дней рождения срабатывает только для миллиарда строк.

Пары удобно класть в set и dict как кортежи. В C++ и Java их часто склеивают в одно 64-битное число: h1 * M2 + h2 или (h1 << 32) | h2.

Сравнение подстрок: LCP и лексикографический порядок

Равенство подстрок за O(1)O(1) — это только начало. Вместе с бинарным поиском хеши дают длину наибольшего общего префикса (LCP) любых двух суффиксов за O(log⁡n)O(\log n).

Идея: если префиксы длины kk совпадают, то совпадают и все более короткие. Значит, «совпадают ли префиксы длины kk» — монотонный предикат, и максимальное kk ищется бинарным поиском по ответу.

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]

Это суффиксный массив за O(nlog⁡2n)O(n \log^2 n) в несколько строк. Специализированные алгоритмы из статьи про суффиксный массив быстрее, но вариант с хешами пишется на собеседовании за пять минут и почти не содержит мест для ошибки.

Типовые задачи

Количество различных подстрок

Для каждой длины положим хеши всех подстрок в множество:

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

Время O(n2)O(n^2) вместо O(n3)O(n^3) при сравнении строк напрямую. Здесь хорошо видно, почему нужен большой модуль: подстрок порядка n2/2n^2 / 2, и при n=5000n = 5000 это уже 12,5 миллиона хешей.

Самая длинная повторяющаяся подстрока

LeetCode 1044 «Longest Duplicate Substring» — задача уровня hard, которая решается бинарным поиском по длине и хешами. Если повтор длины kk есть, то есть и повтор длины k−1k - 1 (отрежем последний символ), так что предикат монотонный.

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

Итог — O(nlog⁡n)O(n \log n). Посимвольная проверка при совпадении хешей страхует от ложного ответа. Её стоимость платится, только когда кандидат найден, после чего функция сразу возвращается, — асимптотику она не портит.

Та же схема находит наибольшую общую подстроку двух строк: для фиксированной длины кладём хеши подстрок первой строки в множество и ищем совпадения среди подстрок второй.

Палиндром ли подстрока

Подстрока — палиндром, если она равна своему развороту. Построим хеши для строки и для её разворота: подстроке 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

Каждый запрос — O(1)O(1). Для одной строки целиком это избыточно (хватит двух указателей), но когда запросов много, хеши выигрывают. Плюс бинарный поиск по радиусу даёт длиннейший палиндром за O(nlog⁡n)O(n \log n) — проще в написании, чем алгоритм Манакера, хотя и медленнее.

Общий префикс нескольких строк

Задача Longest Common Prefix решается и без хешей — посимвольным сравнением за O(S)O(S), где SS — суммарная длина. Но вариант с хешами полезен как упражнение: бинарный поиск по длине, на каждом шаге сравниваем хеши префиксов.

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-функция
Сравнение подстрок, LCPO(1)O(1) / O(log⁡n)O(\log n)суффиксный массив + LCP + sparse table
Различные подстрокиO(n2)O(n^2)суффиксный автомат, O(n)O(n)
ПалиндромыO(nlog⁡n)O(n \log n)Манакер, O(n)O(n)

Детерминированные алгоритмы быстрее и не ошибаются, но каждый из них — отдельная сложная конструкция. Хеши — один универсальный инструмент на 15 строк, который закрывает все строки таблицы. Это и есть их главная ценность: когда точного алгоритма не помните или его долго писать, хеш почти всегда спасает.

Типичные ошибки

Маленький модуль при большом числе сравнений. Модуль 109+710^9 + 7 и 10510^5 хешей в одном множестве — почти гарантированная коллизия. Используйте 261−12^{61} - 1 или двойной хеш.

Переполнение вместо модуля. Хеш по модулю 2642^{64} ломается специально построенным тестом. Беззнаковое переполнение — это не «бесплатный модуль».

Отрицательный остаток. В 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.

Основание меньше алфавита. При p=10p = 10 и кодах символов до 122 разные строки начинают «переносить разряды» и совпадать.

Переполнение в JavaScript. Числа в JS — double, точная целочисленная арифметика заканчивается на 2532^{53}. Произведение двух чисел около 10910^9 уже теряет точность. Берите BigInt или модуль поменьше с двойным хешем, следя, чтобы произведение не превышало 2532^{53}.

pow на каждый запрос. Степени основания предподсчитываются один раз — иначе O(1)O(1) превращается в O(log⁡n)O(\log n).

Где встречается на собеседованиях

Напрямую «напишите полиномиальный хеш» спрашивают редко. Хеш появляется как оптимизация:

  • Repeated DNA Sequences (LeetCode 187) — повторяющиеся подстроки фиксированной длины 10;
  • Longest Duplicate Substring (LeetCode 1044) — бинарный поиск плюс хеши;
  • Distinct Echo Substrings (LeetCode 1316) — подстроки вида aa, проверка половин за O(1)O(1);
  • Shortest Palindrome (LeetCode 214) — самый длинный префикс-палиндром через прямой и обратный хеш;
  • вопросы про дедупликацию документов, сравнение файлов и контрольные суммы в system design.

Хороший ответ включает три вещи: формулу хеша подстроки, оценку вероятности коллизии через парадокс дней рождения и способ защиты — большой модуль, двойной хеш или проверку совпадения напрямую.

Что запомнить

  • Полиномиальный хеш — строка как число в системе с основанием pp по модулю MM.
  • Префиксные хеши и предподсчитанные степени дают хеш любой подстроки за O(1)O(1): H[r]−H[l]⋅pr−lH[r] - H[l] \cdot p^{r-l}.
  • Вероятность коллизии растёт как N2/MN^2 / M, а не N/MN / M. Для 10510^5 строк модуль 10910^9 недостаточен.
  • Надёжные варианты — модуль 261−12^{61} - 1, двойной хеш, случайное основание. Ненадёжный — переполнение 2642^{64}.
  • Хеш + бинарный поиск по длине решает LCP, длиннейший повтор, длиннейший палиндром и сравнение строк.
  • Если цена ошибки высока, проверяйте найденное совпадение посимвольно.

Потренироваться в спокойной обстановке

Все задачи