## 2.4 ALGORITMOS DE EMPATE DE CADENAS

Una cadena es una secuencia de caracteres sobre un alfabeto finito. ATCTAGAGA es un cadena sobre Σ = {A, C, G, T}.

El problema de emparejamiento de cadenas es encontrar todas las ocurrencias de una cadena p, llamada patrón, en una cadena más grande T del mismo alfabeto. Este algoritmo también es conocido como búsqueda de patrones de texto y/o búsqueda de cadenas.

Dadas las cadenas x, y, z, se dice que x es:

> a) Un prefijo de xy,

> b) Un sufijo de yx,

> c) Una subcadena de yxz.

A menudo sucede que los datos a procesar no se descomponen lógicamente en registros independientes que representen pequeñas partes identificables. Este tipo de datos se caracteriza fácilmente por el hecho de que se pueden escribir en forma de cadenas: series lineales (por lo regular muy largas) de caracteres. Las cadenas son evidentemente el centro de los sistemas de tratamiento de texto, que proporcionan una gran variedad de posibilidades para la manipulación de textos.

Tales sistemas procesan cadenas alfanuméricas, que pueden definirse en primera aproximación como series de letras, números y caracteres especiales. Estos objetos pueden ser bastante grandes, por lo que es importante disponer de algoritmos eficaces para su manipulación. Otro tipo de cadena es la cadena binaria, que es una simple serie de valores 0 y 1. Esta es, en cierto sentido, un tipo especial de cadena alfanumérica, pero es útil hacer la distinción porque existen diferentes algoritmos específicos para este tipo de cadenas y porque las cadenas binarias se utilizan en muchas aplicaciones.

Implica la implementación de algoritmos de búsqueda de subcadenas y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. La mayoría de los algoritmos para este problema se pueden modificar fácilmente para encontrar todas las ocurrencias del patrón en el texto, puesto que recorren el texto en secuencia y se pueden reinicializar en la posición situada inmediatamente después del comienzo de una concordancia, para encontrar la concordancia siguiente.

La búsqueda de patrones en un texto es un problema muy importante en la práctica. Sus aplicaciones en computación son variadas, como por ejemplo la búsqueda de una palabra en un archivo de texto o problema relacionados con biología computacional, en donde se requiere buscar patrones dentro de una secuencia de ADN, la cual puede ser modelada como una secuencia de caracteres (el problema es más complejo que lo descrito, puesto que se requiere buscar patrones en donde ocurren alteraciones con cierta probabilidad, esto es, la búsqueda no es exacta).

Para la búsqueda de patrones se utilizan las siguientes convenciones:

- n denotará el largo del texto en donde se buscará el patrón, es decir, texto = a1a2…an.
- m denotará el largo del patrón a buscar, es decir, patrón = b1b2…bm.

###