Hashing polinomiale delle stringhe

Spesso è necessario verificare se due sottostringhe sono uguali. I controlli carattere per carattere sono lenti, quindi si trasforma ogni stringa in un numero. 🔢

Un hash associa una stringa a un singolo numero intero. Se due stringhe sono diverse, quasi sempre anche i loro hash sono diversi.

Si interpreta ogni carattere come una cifra in base p. Questa visione polinomiale trasforma la stringa in una grande somma pesata.

Si scelga una base prima come 31 e un modulo primo grande. Il modulo mantiene piccoli i numeri e previene l'overflow.

Si percorre la stringa e si incorpora ogni carattere usando la regola di Horner, applicando il modulo a ogni passaggio.

Si memorizza un hash del prefisso per ogni posizione. In questo modo l'hash di qualsiasi sottostringa si ottiene con una rapida sottrazione.

Si precalcolano anche le potenze della base. Servono ad allineare i due prefissi quando si esegue la sottrazione.

L'hash di s[l..r] è una sottrazione tra due hash di prefisso, scalata per una potenza. Tempo costante per query.

Due stringhe diverse possono avere lo stesso hash: si parla di una collisione. È raro, ma nei contest a volte vengono creati input per provocarla.

Utilizzi due moduli indipendenti e confronti entrambi gli hash. Una collisione simultanea in entrambi è praticamente impossibile.

L'hashing permette di confrontare sottostringhe, trovare ripetizioni e cercare pattern. È uno strumento versatile, buono per quasi tutto.

Scelga lo strumento giusto per confrontare in sicurezza molte sottostringhe.

Ora può trasformare le stringhe in hash polinomiali, interrogare qualsiasi sottostringa in O(1) e proteggersi dalle collisioni. 🚀