Hachage polynomial de chaînes

Vous devez souvent déterminer si deux sous-chaînes sont égales. Les comparaisons caractère par caractère sont lentes, alors transformons chaque chaîne en un nombre. 🔢

Un hachage associe une chaîne à un entier unique. Si deux chaînes diffèrent, leurs hachages sont eux aussi presque toujours différents.

Nous lisons chaque caractère comme un chiffre en base p. Cette vision polynomiale transforme la chaîne en une grande somme pondérée.

Choisissez une base première comme 31 et un grand modulo premier. Le modulo maintient les nombres à une taille raisonnable et évite les débordements.

Parcourez la chaîne et incorporez chaque caractère avec la règle de Horner, en appliquant le modulo à chaque étape.

Stockez un hachage de préfixe pour chaque position. Le hachage de n’importe quelle sous-chaîne se calcule alors par une soustraction rapide.

Précalculez également les puissances de la base. Elles alignent les deux préfixes lors de la soustraction.

Le hachage de s[l..r] est une soustraction de deux hachages de préfixes, mise à l’échelle par une puissance. Temps constant par requête.

Deux chaînes différentes peuvent avoir le même hachage : c’est une collision. C’est rare, mais les concours construisent parfois des entrées pour la provoquer.

Utilisez deux modules indépendants et comparez les deux hachages. Une collision simultanée dans les deux est pratiquement impossible.

Le hachage permet de comparer des sous-chaînes, de trouver des répétitions et d’effectuer des recherches de motifs. C’est un outil polyvalent.

Choisissez le bon outil pour comparer de nombreuses sous-chaînes en toute sécurité.

Vous savez maintenant transformer des chaînes en hachages polynomiaux, interroger n’importe quelle sous-chaîne en O(1) et vous protéger contre les collisions. 🚀