При решении задач на хеширование вам очень частно бывает надо уметь за $O(1)$ вычислять хеш любой подстроки заданной строки. Стандартный подход к таким задачам — давайте посчитаем хеши всех префиксов, а дальше будем с этим что-то делать…

(Это материал уровня 5 по шкале алгопрога. Если вы не знаете, что такое хеширование и как его применять в олимпиадных задачах, скорее всего, вы мало что поймете в этом тексте.)

…Итак, стандартный подход устроен следующим образом. Начнем немного с начала. Определим хеш строки (хеш-функцию) так:

\[h(s) = s_0 + s_1 \cdot p + s_2 \cdot p^2 + \ldots + s_{n-1} \cdot p^{n-1}.\]

(Все вычисления здесь и ниже подразумеваются по некоторому модулю $M$.)

Посчитаем хеши всех префиксов:

\[H[i] = h(s[0..i]) = s_0 + s_1 \cdot p + \ldots + s_i \cdot p^i\]

Массив $H[i]$ можно насчитать за $O(n)$ очевидным образом ($H[i] = H[i-1] + s_i \cdot p^i$, массив степеней $p$ можно насчитать заранее, будет полезно и в дальнейшем).

Хорошо. Но нам надо знать хеш произвольной подстроки, т.е. $h(s[i..j])$. Очевидно, чтобы его вычислить, нам понадобятся значения $H[i-1]$ и $H[j]$. (Особый случай $i=0$ мы рассматривать не будем, он простой.) Явно напрашивается записать

\[H[j] - H[i-1] = s_i \cdot p^i + \ldots + s_j \cdot p^j = h(s[i..j]) \cdot p^i,\]

но вот проблема — то, что получилось, это не настоящее значение хеш-функции для подстроки $s[i..j]$, а величина, в $p^i$ раз больше. В результате использовать полученное число просто так не получится.

* * *

Есть два стандартных способа решить эту проблему. Первый — хорошо, давайте разделим полученное выражение на $p^i$. Но у нас все вычисления — по модулю $M$, делить в арифметике по модулю возможно не всегда, и в любом случае не очень просто. В простейшем случае, когда $M$ простое, и $p$ (естественно) не делится на $M$, деление возможно и даже не очень сложно (по малой теореме Ферма надо просто умножить на $(p’)^i$, где $p’ = p^{M-2}$; можно заранее вычислить $p’$ и все его степени). Но лишний код писать все равно не охота.

Второй способ — хорошо, давайте поймем, что в конечном счете нам само значение $h(s[i..j])$ не нужно. Как правило, нам надо сравнивать хеши двух подстрок, пусть $s[i..j]$ и $s[i’..j’]$. Мы можем вычислить значения $X=h(s[i..j]) \cdot p^i$ и $Y = h(s[i’..j’]) \cdot p^{i’}$. Напрямую их сравнивать бессмысленно, но мы можем домножить их на подходящие степени, т.е. сравнить $X\cdot p^{i’}$ и $Y\cdot p^i$. Если эти два числа равны, то хеши соответствующих подстрок тоже равны.

Это довольно просто, но не очень красиво. Вы не вычисляете сам хеш, вы вычисляете только какую-то величину, связанную с хешом. При каждом использовании этого хеша вам придется думать, что и как домножать. Ладно если вы только подстроки сравниваете, а если, например, вам надо сделать какую-нибудь мапу, где хеш подстроки является ключом?

Проблема еще и в том, что вам приходится про это помнить и учитывать это в основной программе. Вы бы, возможно, хотели бы написать функцию hash(i, j), которая вам вернет настоящий хеш подстроки $s[i,j]$ (или написать class StringWithHash с соответствущим методом), и дальше в основном коде не думать про то, что хеш не той системы. Но нет, так не получится…

* * *

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

А именно, посчитаем

\[H[i] = h(s[i..n-1]) = s_i + s_{i+1} \cdot p + s_{i+2} \cdot p^2 + \ldots\]

Вычислить такой массив за $O(n)$ тоже очень легко (просто $H[i] = H[i+1] \cdot p + s_i$, эдакий аналог схемы Горнера, даже проще чем раньше — не нужно вычислять $p^i$).

И теперь внимание фокус:

\[h(s[i..j]) = H[i] - H[j+1] \cdot p^{j-i+1}.\]

И это честный хеш. Полученные значения вам уже не надо ни на что домножать, вы можете их сравнивать, можете использовать как ключ в какой-нибудь мапе, и т.д. Вы можете написать class StringWithHash с таким методом, и потом в основной программе уже просто использовать результат вызова метода.

Заодно получили бонусом, что $i=0$ — это не особый случай. Особый случай теперь $j=n-1$, но он обходится легко — делаете $H[n] = 0$ и не надо писать никаких if’ов.

* * *

На самом деле, можно полностью симметрично отразить ситуацию. Выше мы определяли хеш так, что степени $p$ в формуле возрастали слева направо — как будто самый младший разряд «числа» — это его самая левая цифра.

Можно определить хеш строки наоборот:

\[h(s) = s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \ldots + s_{n-1}.\]

Тогда можно посчитать хеши префиксов: $H[i] = h(s[0..i])$ и аналогично можно вычислять честный хеш любой подстроки. (Правда, $i=0$ опять будет особым случаем, но это на самом деле ортогональный вопрос.)

* * *

Выше везде я полагал, что запись $s[i..j]$ включает как символ $i$, так и символ $j$. Можно рассматривать всё, как говорят, на полуинтервалах — символ $i$ включительно, символ $j$ невключительно (аналогично тому, как в питоне устроены срезы). Тогда написание хеширования еще несколько упрощается (например, $i=0$ не будет особым случаем ни при каком подходе). Но это тоже ортогональный вопрос.

* * *

Так что мораль: пишите хеширование без домножения и без деления.

---

Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru