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.
- ¿Cuál es el significado del peor tiempo de ejecución de un algoritmo?
- ¿Podría alguien explicar las etapas de un algoritmo recursivo que muestra cómo se alcanza la condición de terminación?
- Supongamos que eliminamos un borde de un árbol de expansión y luego agregamos un borde diferente para que permanezca conectado. ¿Seguirá siendo un árbol de expansión?
- ¿Cómo funciona el algoritmo de Youtube en términos de tendencias de un video?
- ¿Puedo escribir sobre mi propio algoritmo de clasificación en CV?
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.
