¿Qué es el algoritmo Rabin-Karp?

El algoritmo Rabin-Karp es un algoritmo de coincidencia de patrones de cadenas que busca eficientemente apariciones de un patrón dentro de un texto más grande. Fue desarrollado por Michael O. Rabin y Richard M. Karp en 1987.

El algoritmo utiliza una técnica de hash para comparar los valores hash del patrón y las subcadenas del texto. Funciona de la siguiente manera:

• Calcule el valor hash del patrón y la primera ventana del texto.

• Deslice el patrón sobre el texto una posición a la vez y compare los valores hash.

• Si los valores hash coinciden, compare los caracteres del patrón y la ventana actual del texto para confirmar la coincidencia.

• Si hay una coincidencia, registre la posición/índice de la coincidencia.

• Calcula el valor hash para la siguiente ventana del texto usando una función hash rodante.

• Repita los pasos 3 a 5 hasta que se hayan verificado todas las posiciones del texto.

La función hash continua actualiza de manera eficiente el valor hash para cada nueva ventana restando la contribución del primer carácter en la ventana anterior y sumando la contribución del siguiente carácter en la nueva ventana. Esto ayuda a evitar volver a calcular el valor hash desde cero para cada ventana, lo que hace que el algoritmo sea más eficiente.

Programa PHP para el algoritmo Rabin-Karp para búsqueda de patrones

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

Producción

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Explicación del código

El código PHP implementa el algoritmo Rabin-Karp para la búsqueda de patrones. Toma un patrón y un texto como entradas y busca apariciones del patrón dentro del texto. El algoritmo calcula los valores hash para el patrón y la primera ventana del texto. Luego desliza el patrón sobre el texto, comparando los valores hash de la ventana actual y el patrón. Si los valores hash coinciden, verifica aún más los caracteres uno por uno. Si se encuentra una coincidencia, imprime el índice donde se encuentra el patrón. El algoritmo utiliza una función hash continua para actualizar de manera eficiente el valor hash de cada ventana. El código demuestra el uso del algoritmo buscando el patrón "BC" en el texto "ABCABCABCABCCABC".

Conclusión

En conclusión, el programa PHP implementa eficazmente el algoritmo Rabin-Karp para la búsqueda de patrones. Al utilizar una función hash rodante y comparar valores hash, el algoritmo busca de manera eficiente apariciones de un patrón dentro de un texto más grande. El programa identifica correctamente los índices donde se encuentra el patrón en el texto y genera los resultados. Con una estructura clara y cálculos hash apropiados, el programa demuestra la funcionalidad y utilidad del algoritmo Rabin-Karp para la búsqueda de patrones en PHP.