## 2.4.3 ALGORITMO DE KNUTH-MORRIS-PRATT

El diagrama de flujo KNUTH-MORRIS-PRATT (KMP)

Al construir el autómata finito para un patrón P, es fácil incluir las flechas que corresponden a una coincidencia. Por ejemplo, al dibujar la figura para el patrón ‘AABC’, el primer paso es dibujar:

La parte difícil es la inserción del resto de las flechas. El algoritmo KMP, también construye una especie de diagrama de flujo que se usará para examinar el texto. El diagrama de flujo KMP contiene las flechas fáciles, es decir, las que deber seguirse si se lee del texto el carácter deseado, pero solo contiene una flecha más que sale de cada nodo: la flecha a seguir si el carácter deseado no se leyó del texto. Llamamos a las flechas ligar de éxito y ligas de fracaso, respectivamente.

El diagrama de flujo KMP difiere del autómata finito en varios detalles: los rótulos de caracteres del texto solo después de haber seguido una liga de éxito; si se sigue una liga de fracaso, se volverá a considerar el mismo carácter del texto. Hay un nodo extra que hace que se lea un nuevo carácter de texto; la exploración se inicia en este nodo. Al igual que en el autómata finito, si se llega al nodo rotulado con *, se habrá hallado una copia del patrón; si se llega al final del texto en cualquier otro punto del diagrama de flujo, la exploración terminara sin éxito.

Número de celda KMP | Texto explorado | Éxito (e) ó fracaso (f)
Índice | Carácter
1 | 1 | A | e
2 | 2 | C | f
1 | 2 | C | f
0 | 2 | C | obt. sig. car.
1 | 3 | A | e
2 | 4 | B | e
3 | 5 | A | e
4 | 6 | A | f
2 | 6 | A | e
1 | 6 | A | f
2 | 7 | B | e
3 | 8 | A | e
4 | 9 | B | e
5 | 10 | A | f
3 | 10 | A | e
4 | 11 | ninguno | f

Construcción del diagrama de flujo KMP

La representación del diagrama de flujo es muy sencilla; usamos dos arreglos uno para contener los caracteres del patrón y uno para contener las ligas de fracaso. Las ligas de éxito están implícitas en el ordenamiento de los elementos del arreglo.

Sea fracaso el arreglo de ligas de fracaso; fracaso[k] será el índice del nodo al que apunta la liga de fracaso del k-énesimo nodo, para 1<=k<=m. El nodo especial que simplemente hace que se lea el siguiente carácter se considera el nodo cero; fracaso[1]=0. Para ver cómo establecer las otras ligas de fracaso, consideramos un ejemplo:

Sea P=’ABABABCB’ y supóngase que los primeros seis caracteres han coincidido con seis caracteres consecutivos del texto, como se indica:

Supóngase que el siguiente carácter del texto x, no es una “C”. El siguiente lugar del texto en el que el patrón podría principiar es en la tercera posición que se muestra, es decir:

El patrón se desplaza hacia delante de modo que el segmento inicial más largo que coincida con parte del texto que precede a x quede alineado con esa parte del texto. Ahora se deberá probar x para ver si es una A que coincida con la tercera A del patrón. Por tanto, la liga de fracaso del nodo que contiene la C deberá apuntar al nodo que contiene la tercera A.

El algoritmo de exploración KNUTH-MORRIS-PRATT

Entradas: P y T, las cadenas del patrón y el texto; m, la longitud de p; fracaso, el arreglo de ligas de fracaso establecido con el algoritmo. La longitud de P se habrá determinado al establecer el arreglo fracaso. Se supone que el patrón no está vacío.

Salidas: EL valor devuelto es el incide de T en el que inicia una copia de P, o -1 si no se encuentra P en T.

###