Hash polinómico de cadenas

A menudo necesita comprobar si dos subcadenas son iguales. Compararlas carácter por carácter es lento, así que convertimos cada cadena en un número. 🔢

Un hash asigna una cadena a un único entero. Si dos cadenas son diferentes, sus hashes casi siempre también serán diferentes.

Leemos cada carácter como un dígito en base p. Esta visión polinómica convierte la cadena en una gran suma ponderada.

Elija una base prima, como 31, y un módulo primo grande. El módulo mantiene pequeños los números y evita el desbordamiento.

Recorra la cadena e incorpore cada carácter con la regla de Horner, tomando el módulo en cada paso.

Almacene un hash de prefijo para cada posición. Después, el hash de cualquier subcadena se obtiene mediante una resta rápida.

También debe precalcular las potencias de la base. Estas alinean los dos prefijos al realizar la resta.

El hash de s[l..r] se obtiene restando dos hashes de prefijo y escalando mediante una potencia. Tiempo constante por consulta.

Dos cadenas diferentes pueden compartir un hash; eso es una colisión. Es poco frecuente, pero en los concursos a veces se diseñan entradas para provocarla.

Use dos módulos independientes y compare ambos hashes. Es prácticamente imposible que se produzca una colisión en los dos a la vez.

El hashing permite comparar subcadenas, encontrar repeticiones y buscar patrones. Es una herramienta muy versátil.

Elija la herramienta adecuada para comparar muchas subcadenas de forma segura.

Ahora puede convertir cadenas en hashes polinómicos, consultar cualquier subcadena en O(1) y protegerse contra las colisiones. 🚀