algoritmos de busquedas

ALGORITMOS DE BÚSQUEDAS
Estructura De Datos II
Ricardo Robinson
3-736-747

ALGORITMO DE
Objetivo
 

Knuth-MorrisPratt

Es buscar la existencia de una subcadena dentro de una cadena.

Concepto
Es unalgoritmo de búsqueda de subcadenas.

ALGORITMO DE
Knuth-Morris-Pratt

El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y
de modo independiente por James H. Morris en 1977,pero lo publicaron juntos
los tres.
La ventaja de KMP, es que permite avanzar varias posiciones a la vez, gracias a
la función de fracaso.
Se recomienda usar este algoritmo para la búsqueda de tiposbinarios.

Algoritmo Búsquedakmp:
Entrada: Un Array De Caracteres, T
Un Array De Caracteres, P
Knuth-Morris-Pratt
Definición de variables: un entero, k ← 0 (puntero
de examen en T) un entero,
i ← 0 (laposición del carácter actual en P, y avance relativo respecto de k, para T)
Si tamaño de T es mayor o igual que tamaño de P
entonces precalcular tablakmp(p,f)
mientras k + i es menor que la longitudde T,
hacer si p[i] = t[k + i] entonces
si i es igual a la longitud de P - 1 entonces
devolver k
fin si
asignar i ← i + 1
si no entonces
asignar k ← k + i - f[i]
si i es mayor que 0 entonces asignar i← f[i]
fin si fin si repetir fin si

ALGORITMO DE

ALGORITMO DE
Knuth-Morris-Pratt

DESCRIPCIÓN
• El algoritmo KMP, trata de localizar la posición de comienzo de una cadena,
dentro de otra. Antesque nada con la cadena a localizar se precalcula una
tabla de saltos (conocida como tabla de fallos) que después al examinar
entre si las cadenas se utiliza para hacer saltos cuando se localiza unfallo.
• El objetivo de la tabla (precalculada) de fallo 'F' es no permitir que cada
carácter del array 'T()' sea examinado más de 1 vez.

ALGORITMO DE
Knuth-Morris-Pratt

EFICIENCIA
• Debido a que elalgoritmo precisa de 2 partes donde se analiza una cadena
en cada parte.
• La capacidad del algoritmo queda patente al apreciar como logra saltar
varios caracteres a la vez cuando hay un fallo, cuantos...