Algoritmo Rabin Karp – Hash Negativo
Tengo esta implementación de Rabin-Karp. Ahora, lo único que estoy haciendo para el hash rodante es restar power*source[i] del sourceHash. power es 31^tamaño de target-1 % mod.
Pero no entiendo por qué estamos sumando mod al sourceHash cuando se vuelve negativo. He intentado sumar otros valores, pero no funciona y solo funciona cuando sumamos mod. ¿Por qué es esto? ¿Hay alguna razón específica por la cual estamos sumando mod y no cualquier otra cosa (como un número grande al azar, por ejemplo)?
davy.ai
La razón por la cual estamos agregando
modasourceHashcuando se vuelve negativo es para asegurarnos de que el valor del hash siga siendo positivo y esté dentro del rango de la operación de módulo.La operación de módulo en la programación de computadoras devuelve el residuo al dividir dos números. Si el resultado del cálculo del hash se vuelve negativo, agregar
modasegura que el resultado sea positivo, lo cual es necesario para que la operación de módulo funcione correctamente.Agregar un número grande al azar en lugar de
modpodría causar que el valor del hash esté fuera del rango de la operación de módulo, lo que llevaría a resultados incorrectos.modes un valor fijo y se elige como un número primo cercano al tamaño del alfabeto que se está utilizando (128 en esta implementación).En resumen, agregar
modasegura que el valor del hash siga siendo positivo y esté dentro del rango de la operación de módulo, lo cual es necesario para una correcta coincidencia de cadenas Rabin-Karp.