Hash de Cadenas (String Hashing)

Existen muchos métodos distintos para calcular el hash de cadenas, pero en este curso nos centraremos en uno de los más comunes e intuitivos de implementar. Se utiliza ampliamente en concursos de programación competitiva y en entrevistas de programación.

Imagina que contamos con una cadena s cuyas letras son . Queremos encontrar una forma de calcular fácilmente el hash de cualquier subcadena contigua de s.

Elección de una función de hash sólida

Un ejemplo de una función de hash efectiva en la práctica consiste en tomar cada valor entero de un carácter, multiplicarlo por una potencia de un número primo y, al final, tomar el resultado módulo m:

Aquí tanto p como m son números primos. Por ejemplo, p puede ser 1997, 127, etc. Cuanto más grande sea m, menos probabilidades habrá de colisiones. Sin embargo, si m es demasiado grande, los cálculos pueden volverse más lentos. Por eso, en muchas implementaciones se utiliza 10^9 + 7 o 10^9 + 9. La implementación podría verse así:

s = input()                                  # Entrada del usuario de longitud arbitraria
p = 1997                                     # p: un número primo
m = 1_000_000_007                            # m: un primo lo suficientemente grande

h = [0] * (len(s) + 1)                       # Inicializa h con ceros
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Suma el carácter actual
    h[i + 1] *= p                            # Eleva todas las potencias de p en 1
    h[i + 1] %= m                            # Aplica módulo m en cada iteración

En este fragmento calculamos la función de hash en forma acumulativa para cada índice (puede recordar a un arreglo de sumas prefixadas):

Observa que en esta implementación, el primer índice de h es una variable ficticia igual a 0. Además, cada valor de h depende del anterior:

Cálculo del hash para cualquier subcadena de s

Imagina que queremos comparar dos subcadenas s[l1; r1) y s[l2; r2) de la misma longitud para verificar si son iguales. Necesitamos calcular un hash “normalizado” para cada uno de esos segmentos y, si resultan iguales, declaramos que las subcadenas son idénticas.

Ahora que contamos con la función de hash h, podemos calcular el hash de cualquier subcadena de s. Sin embargo, no se trata simplemente de restar los valores en los índices derecho e izquierdo.

Dado el índice izquierdo l y el índice derecho r, queremos obtener el hash para la subcadena s[l; r). Idealmente, este resultado debería coincidir con el hash obtenido si se hubiera calculado desde cero, únicamente para s[l; r). Como en la fórmula multiplicamos cada carácter por la potencia correspondiente del primo p, debemos ajustar el lado izquierdo del hash en función de la diferencia entre r y l:

Esto es exactamente lo que obtendríamos si calculáramos desde cero el hash de s[l; r) (como si fuera una cadena nueva). Observa que la primera potencia de p corresponde a r-l, que es la longitud de la subcadena, mientras que la última potencia es 1, que coincide con la del último carácter en el cómputo del hash para la cadena completa.

Gracias a esto, cuando comparamos distintos intervalos, por ejemplo [1; 5) y [4; 8), las potencias distintas de p no interfieren en el resultado final. Si los caracteres en [1; 5) son iguales a los de [4; 8), entonces sus hashes deberían coincidir. Para lograrlo, multiplicamos h[l] por la diferencia entre r y l:

# Precalcular las potencias
pows = [1] * (len(s) + 1)                  # Precalcula todas las potencias
for i in range(len(s)):                    # todas las potencias 1...n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Toma el módulo m en cada iteración

# Calcular el hash para [l; r) en O(1)
res = h[r] - h[l] * pows[r - l]            # Ajusta h[l] con la diferencia (r-l)
res %= m                                   # Toma el resultado módulo m
print(res)

Si la cadena de entrada s fuera hello hellyo, los valores de h y pows serían los siguientes, y al realizar algunas consultas, obtendríamos estos resultados:

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

¿Listo para calcular el hash de una cadena y responder consultas sobre el valor del hash en un intervalo específico?

Entrada

La primera línea de la entrada contiene la cadena s (1 ≤ |s| ≤ ).

La segunda línea contiene un entero q (1 ≤ q ≤ 100 000), que representa la cantidad de consultas.

Las siguientes q líneas contienen pares de índices (0 ≤ ≤ |s|).

Salida

El programa debe imprimir el hash de la cadena en el intervalo .

Ejemplos