Хеширование строк (String Hashing)

Существует множество различных методов хеширования строк, но в этом курсе мы рассмотрим один из самых распространенных и интуитивных в реализации. Он широко используется в соревнованиях по программированию и на собеседованиях по алгоритмам.

Представим, что у нас есть строка s с символами . Нам нужен способ, который позволит легко вычислять хеш для любого непрерывного подотрезка строки s.

Выбор надежной хеш-функции

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

Здесь и p, и m — простые числа. В качестве p можно брать любые простые числа, например 1997 или 127. Чем больше m, тем меньше вероятность коллизий. Однако слишком большое m может замедлить вычисления, поэтому часто выбирают m, равное или . Пример кода выглядит так:

s = input()                                  # Пользовательский ввод произвольной длины
p = 1997                                     # p: простое число
m = 1_000_000_007                            # m: достаточно большое простое число

h = [0] * (len(s) + 1)                       # Инициализируем h нулями
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Добавляем текущий символ
    h[i + 1] *= p                            # Увеличиваем все степени p на 1
    h[i + 1] %= m                            # Берем остаток по модулю m на каждой итерации

Таким образом мы вычисляем «прокатный» (rolling) хеш для каждого индекса (это чем-то похоже на массив префиксных сумм):

Обратите внимание, что в этой реализации первый индекс h — это «фиктивная» переменная, равная 0. Кроме того, видно, что каждое значение h зависит от предыдущего:

Вычисление хеша для любого подотрезка строки s

Допустим, мы хотим сравнить два подотрезка s[l1; r1) и s[l2; r2) одинаковой длины и проверить их равенство. Нужно вычислить «нормализованный» хеш для каждого из этих участков и, если хеши совпадут, считать, что подстроки равны.

Мы уже имеем функцию хеширования h, но для вычисления хеша произвольного подотрезка s недостаточно просто взять разность значений на концах отрезка.

Пусть у нас есть левая граница l и правая граница r. Нужно вычислить хеш для подотрезка s[l; r). По сути, нам нужен такой результат, который совпадал бы с хешем, вычисленным «с нуля» — только для подстроки s[l; r). Поскольку мы умножали каждый символ на соответствующую степень простого числа p, следует учесть длину отрезка при «срезании» левой части:

Это ровно то, что мы получили бы, если бы вычислили хеш для s[l; r) отдельно (как для новой строки). Обратите внимание, что первая степень p при этом равна r-l (длина подстроки), а последняя степень равна 1 — именно так мы считаем последнюю букву при хешировании всей строки.

Это гарантирует, что при сравнении разных интервалов, например [1; 5) и [4; 8), различия в степенях p не исказят результат. Если символы на участке [1; 5) такие же, как на [4; 8), мы хотим, чтобы их хеши совпадали. Для этого умножаем h[l] на p^{r - l}:

# Предварительно вычисляем степени
pows = [1] * (len(s) + 1)                  # Предподсчёт всех степеней
for i in range(len(s)):                    # все степени от 1 до n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Берем остаток по модулю m на каждой итерации

# Вычисляем хеш для [l; r) за O(1)
res = h[r] - h[l] * pows[r - l]            # Масштабируем h[l] с учетом длины (r-l)
res %= m                                   # Берем остаток по модулю m
print(res)

Если строка s равна hello hellyo, то массивы h и pows будут следующими, и некоторые запросы дадут такие результаты:

# s ->     h       e          l          l          o                     h          e          l          l          y          o
h    = [0, 207688, 414954633, 664611981, 230332444, 974109122, 295966923, 46148782,  159318707, 159671329, 863857463, 123583173, 795816426]
pows = [1, 1997,   3988009,   964053924, 215672753, 698484731, 873998049, 374091638, 60995857,  808725582, 24975949,  876969810, 308698313]
# i ->  0  1       2          3          4          5          6          7          8          9          10         11         12

# hash for s[0: 3] (hel)    -> 664611981  (l = 0, r = e)
# hash for s[6: 9] (hel)    -> 664611981  (l = 6, r = 9)
# hash for s[0: 5] (hello)  -> 974109122  (l = 0, r = 5)
# hash for s[6: 11] (helly) -> 974129092  (l = 6, r = 11)

Готовы ли вы считать хеш строки и отвечать на запросы вроде «какой будет хеш для заданного подотрезка»?

Ввод

В первой строке входных данных содержится строка s (1 ≤ |s| ≤ ).

Во второй строке дано целое число q (1 ≤ q ≤ 100 000) — количество запросов.

В следующих q строках содержатся пары индексов (0 ≤ ≤ |s|).

Вывод

Программа должна вывести хеш подотрезка строки на отрезке .

Пример