Empate de Cadenas

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.

Fuerza bruta

El método en el que se piensa de inmediato para el reconocimiento de patrones consiste simplemente en verificar, para cada posición posible del texto en la que el patrón pueda concordar, si efectivamente lo hace. 

El algoritmo de Fuerza Bruta compara el patrón con el texto un carácter cada vez, hasta encontrar que no coinciden los caracteres.

Complejidad de Fuerza Bruta

Dado un patrón de M caracteres de longitud, y un texto de N caracteres de longitud.

Mejor caso: encuentra el patrón en las primeras M posiciones del texto.

Complejidad: O(N)

Peor caso: compara el patrón con cada subcadena de texto de longitud M.

Complejidad: O(MN)

Rabin-Karp

Calcula un valor hash para el patrón, y para cada subsecuencia de M-caracteres de texto.

Si los valores hash son diferentes, se calcula una valor para la siguiente secuencia.

Si los valores hash son iguales se usa una comparación de Fuerza Bruta.

Complejidad de Rabin-Karp

Dado un patrón de M caracteres de longitud, y un texto de N caracteres de longitud.

Complejidad Pre-procesamiento: O(M)

Complejidad Búsqueda: O(MN)

Algoritmo Knuth-Morris-Pratt

El algoritmo de búsqueda Knuth-Morris-Pratt (KMP) se diferencia del método de fuerza bruta porque mantiene una pista de información obtenida en comparaciones previas.

Se calcula una función de prefijos (Π) que brinda información sobre el patrón a la hora de hacer las comparaciones. Permite saber el corrimiento sobre el patrón hasta la próxima comparación con algún carácter en el texto, esta información es registrada en una tabla de fallos o tabla de siguientes que dice como realizar las comparaciones en la cadena donde se busca un patrón.

Complejidad : O(n + m

preKMPfunction (Tabla de siguientes)

KMP (Busqueda KMP)

Cuando se detecta una discordancia (no concordancia), el principio donde se comienza a comparar al patrón nuevamente se define por los caracteres que se conocen ya han pasado en el texto (puesto que están en el patrón según lo indica la tabla de siguientes).

Cuando se detecta la no concordancia, se sabe, en virtud del hecho de que concuerdan j caracteres, que no se necesita el puntero i del texto, puesto que ninguno de los j-1 caracteres del texto pueden concordar con el primer carácter del patrón.

Saltar todos los caracteres del patrón cuando se detecta una discordancia, sería un error en el caso en el que el patrón se repita en el propio punto de la concordancia.

Complejidad de Knuth-Morris-Pratt

Dado un patrón de M caracteres de longitud, y un texto de N caracteres de longitud.

Complejidad del calculo de la tabla de fallos: O(M)
Complejidad Búsqueda: O(M+N) 

Boyer-Moore

Fue desarrollado por Bob Boyer y J Strother Moore en 1977.

El algoritmo preprocesa la cadena objetivo que está siendo buscada. El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos.

Generalmente el algoritmo es más rápido cuanto más grande es la cadena que es buscada ya que usa la información conseguida desde un inicio para descartar tantas posiciones del texto como sean posibles. 

Algoritmo con autómata finito

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. 

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

Complejidad de la búsqueda con autómata finito

• Utiliza un AF Determinístico
• Cantidad de Estados = m+1
• Cantidad de Comparaciones = n
• Complejidad Pre-procesamiento: O(m³|Σ|)) 
• Complejidad Búsqueda: O(n)
•