Полиномиальное хеширование - Алгоритмика
Полиномиальное хеширование

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

автор Сергей Слотин
опубликовано 2019

Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хешами.

Будем считать, что строка — это последовательность чисел от $1$ до $m$ (размер алфавита). В C/C++ тип char это на самом деле тоже число (8-битное), поэтому можно вычитать из символов минимальный код и кастовать в число:

int x = (int) (c - 'a' + 1);

Определим прямой полиномиальный хеш строки как значение следующего многочлена:

$$ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \bmod p $$

Здесь $k$ — произвольное число больше размера алфавита, а $p$ — достаточно большой модуль (вообще говоря, не обязательно простой).

Его можно посчитать за линейное время, поддерживая переменную, равную $k$ в нужной степени:

const int k = 31, mod = 1e9+7;

string s = "abacabadaba";
long long h = 0, m = 1;

for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h + m * x) % mod;
    m = (m * k) % mod;
}

Можем ещё определить обратный полиномиальный хеш:

$$ h_b = (s_0 k^n + s_1 k^{n-1} + \ldots + s_n) \mod p $$

Его преимущество в том, что можно писать на одну строчку кода меньше:

long long h = 0;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h * k + x) % mod;
}

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хеш и обозначать его просто буквой $h$.

Зачем это нужно?

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

Например, если нужно посчитать хеш от конкатенации строк $a$ и $b$ (строку $b$ приписали в конец строки $a$), то можно просто хеш $b$ домножить на $k^{|a|}$ и сложить с хешом $a$:

$$ h(ab) = h(a) + k^{|a|} \cdot h(b) $$ Удалить префикс строки можно так: $$ h(b) = \frac{h(ab) - h(a)}{k^{|a|}} $$ А суффикс — ещё проще: $$ h(a) = h(ab) - k^{|a|} \cdot h(b) $$

В задачах нам часто понадобится домножать $k$ в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

const int maxn = 1e5+5;

int p[maxn];
p[0] = 1;

for (int i = 1; i < maxn; i++)
    p[i] = (1ll * p[i-1] * k) % mod; // аккуратно с переполнением

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

int h[maxn];
h[0] = 0; // h[k] -- хеш префикса длины k

// будем считать, что s это уже последовательность int-ов

for (int i = 0; i < n; i++) 
    h[i+1] = (h[i] + p[i] * s[i]) % mod;

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

$$ h(s[l:r]) = \frac{h_r-h_l}{k^l} $$

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хеш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к $n$-ной.

$$ \hat{h}(s[l:r]) = k^{n-l} (h_r-h_l) $$

Так проще — теперь нужно домножать, а не делить:

int hash_substring(int l, int r) {
    return (h[r+1] - h[l]) * p[n-l] % mod;
}

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за $O(1)$.

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

Лайфхак. Если взять обратный полиномиальный хеш короткой строки на небольшом алфавите с $k=10$, то числовое значение хеша строки будет наглядно соотноситься с самой строкой:

$$ h(abacaba)=1213121 $$

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хеши от всех подстрок за $O(n^2)$ и добавим их все в std::set. Чтобы получить ответ, просто вызовем set.size().

Поиск подстроки в строке. Можно посчитать хеши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хеш текущей подстроки. Если хеш какой-то из этих подстрок совпал с хешом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение подстрок на больше-меньше, а не только на равенство. У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше в обеих подстроках возьмём идущий за ним символ и сравним. Это будет работать за $O(\log n)$.

Палиндромность подстроки. Можно посчитать два массива — обратные хеши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно. Это будет работать за $O(n \log n)$, хотя это можно решить и линейно.