¿Cómo funciona la función Rolling Hash utilizada en el algoritmo Rabin Karp?

Considere que hay una Cadena S de tamaño k + 1 de c1 … ck + 1

El hash (H1) sobre k caracteres (c1..ck) podría calcularse de la siguiente manera:
H1 = c1 * a ^ k-1 + c2 * a ^ k-2 + c3 * a ^ k-3 +… + ck * a ^ 0
donde a es una constante
y c1 … ck son caracteres de entrada.

Supongamos que desea calcular el hash (H2) sobre la misma ventana de tamaño k sobre caracteres (c2..ck + 1) podría calcularse a partir de una lógica similar de la siguiente manera:
H2 = c2 * a ^ k-1 + c3 * a ^ k-2 +… + ck + 1 * a ^ 0
donde a es una constante
y c2..ck + 1 son caracteres de entrada.

Ahora, si miramos cuidadosamente, H2 = [H1 * a] + [ck + 1 * a ^ 0 (es decir, el último término de esta ventana)] – [c1 * a ^ k-1 (es decir, primer término de H1)]

Entonces, en efecto, cada vez que estamos calculando hash rodante, no tenemos que calcular completamente el hash. Podemos aprovechar el hash previamente calculado y luego se trata de multiplicar por a, restando el primer término del último hash y agregando el último carácter de la siguiente ventana.

Del mismo modo, cada vez que calcula funciones hash rodantes en las que desplaza la ventana hacia la derecha o hacia la izquierda no implica calcular toda la función hash, sino que requiere multiplicación o división por constante y resta / suma del último / primer término.

Espero que esto ayude.

Mi respuesta La respuesta de Pawan Bhadauria a ¿Qué es un hash rodante y cuándo es útil? debería ayudar

More Interesting

Cómo resolver un problema de puente colgante utilizando circuitos y dónde una persona puede cruzar el puente a la vez

¿Son suficientes los tutoriales del codificador superior de la estructura de datos y los algoritmos para obtener una base sólida en la programación?

¿Cómo se puede averiguar el número de veces que se repite una palabra en una cadena usando Java?

Cómo aprender algoritmos de manera fácil

¿A qué libro se refirió Thomas Cormen mientras estudiaba algoritmos?

¿Cuál es el algoritmo para expulsar a los pasajeros del avión si está sobrevendido?

¿Qué debo aprender en línea si quiero obtener un trabajo bien remunerado en TI en India? ¿Debería ser algo así como algoritmos de estructura de datos o un lenguaje como Python o R o algo así como un desarrollador de aplicaciones de Android o algo más?

¿Cuáles son algunos de los mejores algoritmos?

¿Son los problemas NP completos también problemas NP difíciles? ¿Por qué?

Si solo pudieras usar un algoritmo de Machine Learning para el resto de tu vida, ¿cuál sería?

¿Cómo podemos encontrar el número de subcadenas palindrómicas en una cadena en tiempo lineal?

Si sabemos cómo funciona un algoritmo de hash de contraseña en particular, ¿por qué no podemos simplemente crear una contraseña que genere el mismo hash?

Cómo usar la recursión de la cola de Fibonacci en C ++

Dado un problema, ¿cómo puedo decidir si usar un enfoque codicioso o dividir y conquistar?

¿Cuál es una manera eficiente de crear una gran cantidad de cadenas aleatorias pero únicas?