Algoritmos

Algoritmo de Búsqueda en Texto

Análisis de Algortimos Algoritmo de Búsqueda en Texto

Roberto Sánchez A. @robertoesteban

Universidad Tecnológica INACAP Sede Osorno Ingeniería en Informática17 de Junio de 2010

Roberto Sánchez A.

Análisis de Algoritmos - 1er Semestre 2010

Algoritmo de Búsqueda en Texto

Agenda

1

Algoritmo de Búsqueda en Texto Introducción Algoritmo deFuerza Bruta Algoritmo de Knuth-Morris-Pratt

Roberto Sánchez A.

Análisis de Algoritmos - 1er Semestre 2010

Algoritmo de Búsqueda en Texto

Introducción Algoritmo de Fuerza Bruta Algoritmo deKnuth-Morris-Pratt

Introducción

Criterio en Denición La búsqueda de patrones en un texto es un problema muy importante en la práctica. Sus aplicaciones en computacón son variadas, como porejemplo la búsqueda de una palabra en un archivo de texto o problemas relacionados con biologia computacional, en donde se requiere buscar patrones dentro de una seuencia de ADN, la cual puede sermodelada como una secuencia de caracteres (es problema es mas complejo que lo descrito, puesto que se requiere buscar patrones en donde ocurren alteraciones con cierta probabilidad, esto es, la búsqueda noes exacta)

Roberto Sánchez A.

Análisis de Algoritmos - 1er Semestre 2010

Algoritmo de Búsqueda en Texto

Introducción Algoritmo de Fuerza Bruta Algoritmo de Knuth-Morris-PrattConsideraciones

Utilizar las siguientes convenciones

n denotará el largo del texto en donde se buscará el patrón, es decir, texto = a1 a2 ... an . m denotará el largo del patrón a buscar, es decir,patron = b1 b2 ... bm . Texto= analisis de algoritmo Patron= algo

Ejemplo

Roberto Sánchez A.

Análisis de Algoritmos - 1er Semestre 2010

Algoritmo de Búsqueda en Texto

IntroducciónAlgoritmo de Fuerza Bruta Algoritmo de Knuth-Morris-Pratt

Consideraciones

Utilizar las siguientes convenciones

n denotará el largo del texto en donde se buscará el patrón, es decir, texto = a1...