Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хешами.
Будем считать, что строка — это последовательность чисел от $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)$, хотя это можно решить и линейно.