String Hashing

Esistono molti metodi per il calcolo dell’hash di una stringa, ma in questo corso ci concentreremo su uno dei più comuni e intuitivi da implementare. È ampiamente utilizzato nei concorsi di programmazione competitiva e nei colloqui algoritmici.

Immaginiamo di avere una stringa s con caratteri . Vogliamo trovare un metodo che ci consenta di calcolare facilmente l’hash per qualsiasi sottostringa contigua di s.

Scelta di una funzione hash solida

Un esempio di funzione hash affidabile e che funziona bene nella pratica prevede di moltiplicare il valore numerico di ogni carattere per una potenza di un numero primo e poi di prendere il risultato modulo m:

Qui sia p sia m sono numeri primi. p può essere un numero primo qualunque, ad esempio 1997 o 127. Più m è grande, minore è la probabilità di collisione, ma scegliere m troppo grande può rallentare i calcoli. Per questo motivo, molte implementazioni usano o . Un’implementazione possibile è la seguente:

s = input()                                  # Input dell’utente di lunghezza arbitraria
p = 1997                                     # p: un numero primo
m = 1_000_000_007                            # m: un numero primo sufficientemente grande

h = [0] * (len(s) + 1)                       # Inizializza h a 0
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Aggiunge il carattere corrente
    h[i + 1] *= p                            # Eleva tutte le potenze di p di 1
    h[i + 1] %= m                            # Prende modulo m a ogni iterazione

Qui calcoliamo la funzione di rolling hash per ogni indice (in modo simile a un array di somme prefisse):

Da notare che in questa implementazione il primo indice di h è una variabile fittizia pari a 0. Inoltre, possiamo vedere che ogni valore h dipende dal precedente:

Calcolo dell’hash per qualsiasi sottostringa di s

Supponiamo di voler confrontare due sottostringhe s[l1; r1) e s[l2; r2) della stessa lunghezza per verificarne l’uguaglianza. Vogliamo calcolare un hash normalizzato per ciascuno di questi segmenti e, se questi hash risultano uguali, affermiamo che le sottostringhe sono uguali.

Ora che abbiamo la funzione hash h, siamo in grado di calcolare l’hash di qualunque sottostringa di s. Tuttavia, non è banale come prendere la differenza tra l’indice di destra e quello di sinistra.

Dato l’indice sinistro l e l’indice destro r, vogliamo calcolare l’hash della sottostringa s[l; r). In modo ideale, il risultato dovrebbe coincidere con l’hash ottenuto calcolando l’hash sulla sola sottostringa s[l; r) come se fosse una stringa nuova. Poiché abbiamo moltiplicato ogni carattere per la potenza corrispondente di p, dobbiamo “aggiustare” la parte sinistra dell’hash tenendo conto della differenza r - l:

Questo è esattamente il risultato che si otterrebbe calcolando da zero l’hash per s[l; r) (come stringa completamente nuova). Osserviamo che la prima potenza di p vale r-l, cioè la lunghezza della sottostringa, mentre l’ultima potenza è 1, esattamente come succede nell’hash dell’intera stringa per l’ultimo carattere.

In questo modo, se calcoliamo l’hash per intervalli diversi come [1; 5) e [4; 8), le diverse potenze di p non influiscono sul risultato finale. Se i caratteri dell’intervallo [1; 5) sono gli stessi di quelli dell’intervallo [4; 8), vogliamo che i loro hash coincidano. Possiamo farlo moltiplicando h[l] per la differenza tra r e l:

# Precomputa le potenze
pows = [1] * (len(s) + 1)                  # Precalcola tutte le potenze
for i in range(len(s)):                    # tutte le potenze 1...n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Prende modulo m a ogni iterazione

# Calcola l’hash per [l; r) in O(1)
res = h[r] - h[l] * pows[r - l]            # Scala h[l] in base alla differenza (r-l)
res %= m                                   # Applica il modulo m al risultato
print(res)

Se la stringa di input s è hello hellyo, i valori di h e pows potrebbero essere i seguenti, e alcune query di esempio darebbero questi risultati:

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

Siete pronti a effettuare l’hashing di una stringa e rispondere a query come “Qual è l’hash di una specifica sottostringa?”?

Input

La prima riga dell’input contiene la stringa s (1 ≤ |s| ≤ ).

La seconda riga contiene un singolo intero q (1 ≤ q ≤ 100 000), che rappresenta il numero di query.

Le successive q righe contengono coppie di indici (0 ≤ ≤ |s|).

Output

Il programma dovrà stampare l’hash della stringa nell’intervallo .

Examples