La búsqueda de cadenas es un proceso fundamental en computación que consiste en localizar la posición inicial de una cadena secundaria (llamada patrón) dentro de una cadena principal (llamada texto). Si el patrón existe, se devuelve su índice inicial; de lo contrario, se retorna un valor negativo, usualmente -1.

Algoritmo de Fuerza Bruta (Brute Force)

Este enfoque, también conocido como búsqueda exhaustiva, compara el patrón con el texto posición por posición. Si ocurre una discrepancia (mismatch), el puntero del texto retrocede al siguiente carácter desde donde comenzó la comparación anterior, y el puntero del patrón se reinicia a cero.

Lógica de funcionamiento

1. Se recorren simultáneamente el texto y el patrón mediante índices.
2. Si los caracteres coinciedn, ambos índices avanzan.
3. Si hay una diferencia, el índice del texto vuelve a la posición inicio_actual + 1 y el índice del patrón regresa al principio.
4. El proceso termina cuando se encuentra el patrón o se agota el texto.

int buscar_fuerza_bruta(const char *texto, const char *patron, int p_inicial) {
   int tam_texto = strlen(texto);
   int tam_patron = strlen(patron);
   
   int i = p_inicial; // Índice para el texto
   int j = 0;         // Índice para el patrón

   while (i < tam_texto && j < tam_patron) {
       if (texto[i] == patron[j]) {
           i++;
           j++;
       } else {
           // Retroceso: i vuelve al siguiente punto de inicio, j a cero
           i = i - j + 1;
           j = 0;
       }
   }

   if (j == tam_patron) {
       return i - j; // Coincidencia encontrada
   }
   return -1;
}
   

Algoritmo Knuth-Morris-Pratt (KMP)

El algoritmo KMP optimiza la búsqueda evitando el retroceso innecesario en la cadena de texto. Se basa en la observación de que, cuando ocurre un fallo, el patrón mismo contiene información suficiente para determinar dónde podría comenzar la siguiente coincidencia válida.

El vector Next

Para evitar retroceder en el texto, el KMP utiliza una tabla de preprocesamiento llamada next. Esta tabla almacena la longitud del prefijo más largo que también es un sufijo para cada subcadena del patrón.

Implementación de la tabla de fallos

int* calcular_tabla_next(const char *patron, int m) {
   int *tabla = (int*)malloc(sizeof(int) * m);
   if (!tabla) return NULL;

   tabla[0] = -1;
   if (m > 1) tabla[1] = 0;

   int actual = 1;
   int prefijo = 0;

   while (actual < m - 1) {
       if (prefijo == -1 || patron[actual] == patron[prefijo]) {
           actual++;
           prefijo++;
           tabla[actual] = prefijo;
       } else {
           prefijo = tabla[prefijo];
       }
   }
   return tabla;
}
   

Búsqueda KMP optimizada

Al utilizar la tabla next, cuando se detecta una diferencia, el índice del texto permanece estático mientras que el índice del patrón se desplaza a la posición indicada por la tabla.

int buscar_kmp(const char *texto, const char *patron, int pos_inicio) {
   int n = strlen(texto);
   int m = strlen(patron);
   
   if (m == 0) return 0;

   int *next = calcular_tabla_next(patron, m);
   int i = pos_inicio; 
   int j = 0;

   while (i < n && j < m) {
       if (j == -1 || texto[i] == patron[j]) {
           i++;
           j++;
       } else {
           j = next[j]; // Desplazamiento inteligente del patrón
       }
   }

   free(next);
   return (j == m) ? (i - j) : -1;
}
   

Optimización NextVal

Existe una mejora adicional denominada nextval. Si el carácter en la posición de retroceso es idéntico al carácter que causó el fallo, el retroceso sigue fallando de la misma manera. nextval soluciona esto saltando directamente a una posición que tenga un carácter diferente.

int* calcular_tabla_nextval(const char *patron, int m) {
   int *next = calcular_tabla_next(patron, m);
   int *nextval = (int*)malloc(sizeof(int) * m);
   
   nextval[0] = -1;
   for (int i = 1; i < m; i++) {
       // Si el carácter actual es igual al de su posición de retroceso
       if (patron[i] == patron[next[i]]) {
           nextval[i] = nextval[next[i]];
       } else {
           nextval[i] = next[i];
       }
   }
   
   free(next);
   return nextval;
}