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

(Это кросс-пост поста из моего блога.)

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

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

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

Массив $$$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$$$ мы рассматривать не будем, он простой.) Явно напрашивается записать

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

* * *

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

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

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

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

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

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

* * *

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

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

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

* * *

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

* * *

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