Explique el principio de funcionamiento del algoritmo de búsqueda de subcadenas de Knuth-Morris-Pratt.
sobes.tech AI
Respuesta de la IA
El algoritmo de Knuth-Morris-Pratt (KMP) está diseñado para buscar una subcadena en una cadena en tiempo lineal, evitando comparaciones repetidas de caracteres.
La idea principal es calcular previamente para la subcadena un array de funciones de prefijo (o "array π"), que muestra cuántos caracteres coinciden con el inicio de la subcadena en una comparación fallida. Esto permite, en caso de no coincidencia, no volver al inicio en la cadena original, sino desplazar la subcadena en la cantidad óptima de posiciones.
Ejemplo:
- Texto: "ABABDABACDABABCABAB"
- Buscando la subcadena: "ABABCABAB"
El algoritmo primero construye la función de prefijo para la subcadena, luego recorre el texto comparando los caracteres. En caso de no coincidencia, usa la función de prefijo para determinar con qué carácter de la subcadena continuar la comparación, sin empezar desde el principio.
Esto garantiza una complejidad de O(n + m), donde n es la longitud del texto, m es la longitud de la subcadena, siendo más eficiente que la búsqueda ingenua.