Algoritmo Kmp

Informe
Análisis de algoritmo:
Algoritmo de búsqueda KMP.

Profesor: Roberto Sánchez
Integrantes: Cristian Vargas, Denny Barría

ALGORITMO KMP (KNUTH-MORRIS-PRATT)
El algoritmo KMP tiene porobjeto buscar la existencia de palabra dentro de una cadena de texto. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contienede sí (sobre ella se precalcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.
Elalgoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada con la cadena a localizar se precalcula una tabla de saltos (conocida como tabla de fallos) quedespués al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo.
Algoritmo proceso previo
INICIO
PP[0]=0
J=0;
I=0;
WHILE ( I < M)
IF ( P [I] == P [J];PP[I] = J + 1;
I + +;
J + +;
ELSE
IF ( J > 0)
J = PP [J – 1]
ELSE
PP [I] = 0;
I ++ ;
RETURN PP;

Ejemplo del proceso previo o tabla de fallos
J 0 1 2 3 4 5 6 7
P[J] C O CA C O L A


I 0 1 2 3 4 5 6 7
P[I] C O C A C O L A


PP[I] 0 0 0 0 1 2 0 1

EJEMPLO 2
J 0 1 2 3 4 5
P[J] A A B A A A

I 0 1 2 3 4 5
P[I] A A B A A A

PP[I] 0 1 0 1 2 2

Cómofunciona el algoritmo KMP:
El alogoritmo realiza comparaciones del patrón y del texto principal, utilizando un puntero en la cadena principal y otro puntero en la cadena en la que se encuentra elpatrón.
I 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
T[i] A C O C A C O C A C O C O C A C O L A
C

P[j] C O C A C O L A
PP 0 0 1 0 1 2 0 0
J 0 1 2 3 4 5 6 7
El algoritmorealiza la primera comparación, como T[i]!=P[j] entonces el patrón avanza un lugar en la búsqueda y la reanuda siguiente posición.

I 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
T[i] A C O C A C O C...