String Hashing

Existem diversos métodos para hashing de strings, mas neste curso vamos focar num dos mais comuns e intuitivos de implementar. É amplamente utilizado em competições de programação e em entrevistas de algoritmos.

Imagine que temos uma string s com as letras . Queremos obter uma forma de calcular facilmente o hash de qualquer substring contígua de s.

Picking a Strong Hash Function

Um exemplo de função de hash robusta que funciona na prática é aquela que pega uma string, multiplica o valor inteiro de cada carácter por uma potência de um número primo e toma o resultado módulo m:

Aqui, tanto p como m são números primos. p pode ser um primo como 1997, 127, etc. Quanto maior for m, menor a probabilidade de colisão. No entanto, escolher um m demasiado grande pode tornar os cálculos mais lentos. Por isso, muitas implementações usam m = 10^9 + 7 ou m = 10^9 + 9. Isto pode ser implementado assim:

s = input()                                  # Entrada do utilizador com comprimento arbitrário
p = 1997                                     # p: um número primo
m = 1_000_000_007                            # m: um número primo suficientemente grande

h = [0] * (len(s) + 1)                       # Inicializar h com zeros
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Adicionar o carácter atual
    h[i + 1] *= p                            # Aumentar todas as potências de p em 1
    h[i + 1] %= m                            # Tomar módulo m a cada iteração

Aqui, estamos a calcular a função de rolling hash para cada índice (que pode assemelhar-se a um array de prefix sums):

Note que, nesta implementação, o primeiro índice de h é uma variável fictícia igual a 0. Além disso, cada valor de h depende do anterior:

Computing the Hash for Any Substring of s

Suponhamos que queremos comparar duas substrings s[l1; r1) vs s[l2; r2) de mesmo comprimento para verificar se são iguais. O objetivo é calcular um hash normalizado para cada intervalo e, se esses hashes forem iguais, dizemos que as substrings são iguais.

Agora que já temos a função de hash h, podemos calcular o hash de qualquer substring de s. Porém, não é tão simples quanto subtrair o valor do índice direito pelo do índice esquerdo.

Dado o índice esquerdo l e o índice direito r, queremos calcular o hash para a substring s[l; r). Idealmente, gostaríamos que o hash resultante fosse igual ao obtido se calculássemos o hash “do zero” – apenas na substring s[l; r). Visto que multiplicámos cada carácter pela potência correspondente do primo p, devemos ajustar a parte esquerda do hash pela diferença entre r e l:

Isto é exatamente o que obteríamos se calculássemos o hash para s[l; r) de forma independente (como uma nova string). Repare que o primeiro termo de p tem a potência r-l, correspondente ao comprimento da substring, enquanto o último termo tem a potência 1, que corresponde ao que teríamos para a última letra no cálculo do hash para a string completa.

Isso garante que, ao calcular a função de hash para intervalos diferentes, como [1; 5) vs [4; 8), as diferentes potências de p não alterem o resultado final. Se os caracteres no intervalo [1; 5) forem os mesmos que no intervalo [4; 8), queremos que os respetivos hashes sejam iguais. Isto pode ser feito multiplicando h[l] pela diferença entre r e l:

# Pré-calcular as potências
pows = [1] * (len(s) + 1)                  # Pré-calcular todas as potências
for i in range(len(s)):                    # potências 1...n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Tomar módulo m a cada iteração

# Calcular o hash para [l; r) em O(1)
res = h[r] - h[l] * pows[r - l]            # Escalar h[l] pela diferença (r-l)
res %= m                                   # Tomar módulo m do resultado
print(res)

No caso da string s ser hello hellyo, os valores de h e pows seriam os seguintes, e efetuar algumas consultas resultaria nos valores abaixo:

# 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)

Está pronto para criar o hash de uma string e responder a consultas sobre qual seria o hash de um determinado intervalo?

Entrada

A primeira linha da entrada contém a string s (1 ≤ |s| ≤ ).

A segunda linha contém um único inteiro q (1 ≤ q ≤ 100 000), que representa o número de consultas.

As q linhas seguintes contêm pares de índices (0 ≤ ≤ |s|).

Saída

O programa deve imprimir o hash da string no intervalo .

Exemplos