CURSO 2008-2009
TRABAJOS de RECONOCIMIENTO DE
PATRONES
ÁRBOLES DE SUFIJOS
ALFONSO ROA
En este trabajo se plantea resolver los siguientes problemas
mediante el uso de árboles de sufijos:
-
El problema de la búsqueda exacta de
patrones (el problema clásico de RP), esto es, encontrar
cuántas veces está un patrón P está
en un texto T.
- El problema de la subcadena para una base de datos de patrones. Este
problema consiste en encontrar una cadena S en una base de datos de
patrones P1, ..., Pk. Se trata de una generalización del problema
clásico de RP.
- El problema de las repeticiones maximales. Dada una cadena S se quiere
encontrar la subcadena de S de mayor longitud que aparece exactamente
dos veces. Esta subcadena se denomina repetición maximal de S,
y no es única necesariamente.
Para estos problemas se dan los siguientes ficheros:
PROBLEMA 1: Búsqueda exacta de patrones.
PROBLEMA 2: El problema de la subcadena para una base
de datos de patrones. Todos los problemas tienen alfabeto Adn.
PROBLEMA 3: El problema de las repeticiones maximales. Se dan tres
cadenas en las que hay que buscar las repeticiones maximales.
|
