Búsqueda de subcadenas (4): algoritmo Rabin-Karp

El algoritmo Rabin-Karp es un algoritmo de búsqueda de cadenas basado en hash inventado por M.O. Rabin y R.A.

Los pasos para una búsqueda de cadenas basada en hash suelen ser:

Pero este método es más lento que una búsqueda de fuerza bruta porque el cálculo del valor hash involucra cada carácter de la cadena. Rabin y Karp mejoraron el método anterior e inventaron un método que puede calcular una subcadena de M caracteres en tiempo constante.

Tome el texto "3141592653589793" y la cadena de patrón "26535" como ejemplo.

La idea de comparación es la siguiente:

Encuentre un número primo grande (como el tamaño de la tabla hash) y luego calcule el valor hash de la cadena del patrón mediante la "división por el método del resto". Luego, los valores hash de subcadenas de la misma longitud en el texto se calculan secuencialmente para compararlos.

Valor hash de cadena de texto recursivo:

Sea Ti representa el carácter de texto T[i] y X i representa la cadena de texto con valor entero T[i.... . M-1-i], donde M es la longitud de la cadena del patrón, entonces:

Mediante recursividad podemos obtener:

Inicialmente podemos encontrar la cadena T[i.. . M-1-i], es decir, Cadena T[i 1.... M-i], es decir, X i 1 P.

El código fuente completo del algoritmo RK: ​​

El algoritmo Rabin-Karp tiene ciertos conflictos porque compara la igualdad calculando el valor hash de la cadena de patrón y la subcadena de texto. que los hash son iguales, pero las cadenas no coinciden.

La probabilidad de conflicto está relacionada con la selección de números primos grandes, y la probabilidad es de aproximadamente 1/Q (Q es el valor de los números primos grandes en aplicaciones prácticas, el algoritmo es confiable y el). La probabilidad de conflicto es muy pequeña.