Algoritmo De Busqueda En Texto

 Knuth-Morris-Pratt (KMP)

• La idea de este algoritmo, consiste en utilizar heurísticas (trata de métodos exploratorios durante la resolución deproblemas) para reducir el número de comparaciones entre caracteres realizadas durante la búsqueda.

• Pertenece a la familia de algoritmos Morris-Pratt. Mejorael algoritmo de fuerza bruta, tratando de evitar comparaciones ya hechas en una iteración anterior. Al igual que fuerza bruta, puede buscar cadenas decualquier longitud, por lo que lo podríamos utilizar para encontrar frases extensas.


x: patrón buscado

y: texto de búsqueda

Para entender sufuncionamiento, supongamos que estamos buscando el patrón x en el texto y. En una determinada iteración hemos encontrado coincidencias hasta la posición i + j, en laque los caracteres b y a difieren.

Por lo tanto no hay emparejamiento y es necesario desplazar x para iniciar una nueva iteración. Para ello buscamos sialgún sufijo de la región u es a la vez prefijo de la misma u. Si eso es así, en la siguiente iteración colocamos el patrón x de modo que el prefijo y sufijocoincidan; los caracteres pertenecientes a esta región coincidente (que en la figura se denominan v) no precisan ser comparados de nuevo. Si no existe ningúnsufijo de u que sea también su prefijo, al desplazar el patrón lo situaremos alineando su primer carácter con el carácter b de la cadena como lo muestra lafigura posterior Al no existir región v en este caso, tendremos asegurado no estar perdiendo ninguna posible coincidencia.

Fuente: Carlos Avendaño Pérez