Hachage de chaînes

Il existe de nombreuses méthodes différentes pour le hachage de chaînes, mais dans ce cours, nous allons aborder l’une des approches les plus courantes et intuitives à mettre en œuvre. Elle est très utilisée dans les concours de programmation compétitive et lors d’entretiens algorithmiques.

Imaginons que nous ayons une chaîne s composée des lettres s_0, s_1, ..., s_{n-1}. Nous souhaitons disposer d’une méthode nous permettant de calculer facilement le hachage de n’importe quelle sous-chaîne contiguë de s.

Choisir une fonction de hachage robuste

Un exemple d’une fonction de hachage solide, efficace dans la pratique, consiste à prendre une chaîne, multiplier chaque valeur entière de caractère par une puissance d’un certain nombre premier, puis à prendre le résultat modulo m :

Ici, à la fois p et m sont des nombres premiers. p peut être n’importe quel nombre premier, comme 1997 ou 127. Plus m est grand, moins il est probable de produire une collision. Cependant, choisir un m trop grand peut ralentir les calculs. C’est pourquoi de nombreuses implémentations prennent m = 10^9 + 7 ou 10^9 + 9. Voici un exemple d’implémentation :

s = input()                                  # User input of arbitrary length
p = 1997                                     # p: a prime number
m = 1_000_000_007                            # m: a sufficiently large prime

h = [0] * (len(s) + 1)                       # Initialize h with 0s
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Add the current character
    h[i + 1] *= p                            # Raise all the powers of p by 1
    h[i + 1] %= m                            # Take modulo m on every iteration

Ici, nous calculons la fonction de hachage « à déroulement » (rolling hash) pour chaque index (ce qui peut rappeler le fonctionnement d’un tableau de sommes préfixes) :

Notez que dans cette implémentation, le premier indice de h est une variable factice égale à 0. De plus, on remarque que chaque valeur de h dépend de la précédente :

Calcul du hachage pour n’importe quelle sous-chaîne de s

Supposons que nous voulions comparer deux sous-chaînes s[l1; r1) et s[l2; r2) de même longueur pour vérifier leur égalité. Nous souhaitons calculer un hachage « normalisé » pour chacune de ces portions et, si ces hachages coïncident, nous conclurons que les deux sous-chaînes sont identiques.

Maintenant que nous avons la fonction de hachage h, nous pouvons calculer le hachage de n’importe quelle sous-chaîne de s. Toutefois, ce n’est pas aussi simple que de prendre la différence entre l’indice de droite et l’indice de gauche.

Étant donné l’indice gauche l et l’indice droit r, nous voulons calculer le hachage pour la sous-chaîne s[l; r). Idéalement, nous aimerions que le résultat soit identique à celui que nous obtiendrions en calculant le hachage uniquement sur s[l; r) depuis zéro. Puisque nous avons multiplié chaque caractère par la puissance correspondante du premier p, il faut ajuster la partie gauche du hachage en fonction de la différence entre r et l :

C’est exactement le résultat que nous obtiendrions si nous recréions le hachage de la sous-chaîne s[l; r) comme une nouvelle chaîne. Remarquez que la première puissance de p est r-l, correspondant à la longueur de la sous-chaîne, tandis que la dernière puissance est 1, ce qui coïncide avec la puissance de la dernière lettre lors du calcul de hachage de la chaîne entière.

Cela garantit que lors du calcul de la fonction de hachage pour différents intervalles comme [1; 5) et [4; 8), les différentes puissances de p n’influencent pas le résultat final. Si les caractères présents dans [1; 5) sont les mêmes que dans [4; 8), nous souhaitons que leurs hachages soient identiques. Pour cela, il suffit de multiplier h[l] par la différence r - l :

# Pré-calculer les puissances
pows = [1] * (len(s) + 1)                  # Pré-calculer toutes les puissances
for i in range(len(s)):                    # toutes les puissances de 1...n
    pows[i + 1] = pows[i] * p              # p^i = p^(i-1) * p
    pows[i + 1] %= m                       # Prendre le modulo m à chaque itération

# Calculer le hachage pour [l; r) en O(1)
res = h[r] - h[l] * pows[r - l]            # Adapter h[l] en fonction de la différence (r-l)
res %= m                                   # Prendre le résultat modulo m
print(res)

Si la chaîne s saisie est hello hellyo, les valeurs de h et pows ressembleront à ce qui suit, et certaines requêtes donneront les résultats indiqués :

# 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
# hash for s[6: 9] (hel)    -> 664611981
# hash for s[0: 5] (hello)  -> 974109122
# hash for s[6: 11] (helly) -> 974129092

Êtes-vous prêt à hacher une chaîne et à répondre à des requêtes telles que : « quel est le hachage pour une sous-chaîne donnée ? »

Entrée

La première ligne de l’entrée contient la chaîne s (1 ≤ |s| ≤ 10^6).

La deuxième ligne contient un entier q (1 ≤ q ≤ 100 000) qui représente le nombre de requêtes.

Les q lignes suivantes contiennent des paires d’indices l_i, r_i (0 ≤ l_i, r_i ≤ |s|).

Sortie

Le programme doit afficher le hachage de la chaîne sur l’intervalle [l_i; r_i).

Exemples