String Hashing

Es gibt viele verschiedene Methoden zum String Hashing. In diesem Kurs besprechen wir jedoch eine der gängigsten und intuitivsten Implementierungen. Sie wird häufig in Wettbewerben und algorithmischen Vorstellungsgesprächen verwendet.

Stellen wir uns vor, wir haben einen String s mit den Buchstaben . Wir möchten eine Methode entwickeln, mit der wir den Hash für jeden beliebigen zusammenhängenden Teilstring von s leicht berechnen können.

Picking a Strong Hash Function

Ein Beispiel für eine in der Praxis gut funktionierende Hash-Funktion ist eine Funktion, die jeden Zeichenwert multipliziert mit einer Potenz einer Primzahl und anschließend modulo m nimmt:

Hier sind sowohl p als auch m Primzahlen. p kann eine beliebige Primzahl sein, zum Beispiel 1997 oder 127. Je größer m, desto geringer ist die Wahrscheinlichkeit einer Kollision. Wählt man m jedoch zu groß, kann es die Berechnungen verlangsamen. Aus diesem Grund setzen viele Implementierungen m auf oder . Das kann wie folgt implementiert werden:

s = input()                                  # Benutzereingabe beliebiger Länge
p = 1997                                     # p: eine Primzahl
m = 1_000_000_007                            # m: eine ausreichend große Primzahl

h = [0] * (len(s) + 1)                       # h mit Nullen initialisieren
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Aktuelles Zeichen hinzufügen
    h[i + 1] *= p                            # Alle Potenzen von p um 1 erhöhen
    h[i + 1] %= m                            # Nach jeder Iteration modulo m nehmen

Hier berechnen wir die Rolling-Hash-Funktion für jeden Index (das ähnelt einem Prefix-Summen-Array):

Beachte, dass der erste Index von h hier ein Platzhalter ist und den Wert 0 hat. Außerdem hängt jeder h-Wert vom vorherigen ab:

Computing the Hash for Any Substring of s

Angenommen, wir möchten zwei Teilstrings s[l1; r1) und s[l2; r2) gleicher Länge vergleichen und überprüfen, ob sie identisch sind. Wir wollen einen normalisierten Hash für jeden dieser Abschnitte berechnen. Falls diese Hashes übereinstimmen, nehmen wir an, dass auch die Teilstrings gleich sind.

Da wir nun die Hash-Funktion h haben, können wir den Hash für jeden beliebigen Teilstring von s berechnen. Allerdings ist es nicht so einfach, nur die Differenz zwischen rechtem und linkem Index zu bilden.

Gegeben der linke Index l und der rechte Index r, möchten wir den Hash für den Teilstring s[l; r) bestimmen. Idealerweise soll der resultierende Hash dem entsprechen, den wir erhalten würden, wenn wir den Hash nur für diesen Teilstring s[l; r) von Grund auf berechnen. Da jedes Zeichen mit der entsprechenden Potenz der Primzahl p multipliziert wurde, muss der linke Teil entsprechend angepasst werden, indem wir die Differenz zwischen r und l berücksichtigen:

Genau das entspräche dem Ergebnis, wenn wir den Hash für s[l; r) neu (als komplett eigenen String) berechnet hätten. Dabei trägt das erste Zeichen im Hash die Potenz r-l, also die Länge des Teilstrings, und das letzte Zeichen die Potenz 1, was genau der Reihenfolge beim Hashen des gesamten Strings entspricht.

Damit die verschiedenen Potenzen von p für unterschiedliche Intervalle wie [1; 5) vs. [4; 8) nicht das Endergebnis beeinflussen, wird h[l] entsprechend der Differenz (r - l) skaliert:

# Potenzen vorberechnen
pows = [1] * (len(s) + 1)                  # Alle Potenzen vorrechnen
for i in range(len(s)):                    # für alle Potenzen 1...n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Nach jeder Iteration modulo m nehmen

# Berechnung des Hashes für [l; r) in O(1)
res = h[r] - h[l] * pows[r - l]            # Skaliert h[l] um (r-l)
res %= m                                   # Ergebnis modulo m nehmen
print(res)

Wenn zum Beispiel der Eingabestring s den Wert hello hellyo hat, sehen die Werte von h und pows so aus, und Anfragen liefern etwa folgende Resultate:

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

Seid ihr bereit, einen String zu hashen und Anfragen abzuwickeln, beispielsweise welcher Hash einem bestimmten Teilstring entspricht?

Input

Die erste Zeile der Eingabe enthält den String s (1 ≤ |s| ≤ ).

Die zweite Zeile enthält eine ganze Zahl q (1 ≤ q ≤ 100 000), die die Anzahl der Anfragen angibt.

Die nächsten q Zeilen enthalten die Indexpaare (0 ≤ ≤ |s|).

Output

Das Programm soll den Hash des Strings im Intervall ausgeben.

Beispiele