Algoritmo de búsqueda de cadenas (String Search) en C++: explicación, ejemplo y código

El algoritmo de búsqueda de cadenas se utiliza para encontrar ocurrencias de un patrón específico(subcadena) dentro de un texto más grande(cadena). Este algoritmo juega un papel crucial en las tareas de procesamiento, búsqueda y manipulación de texto.

Cómo funciona

1. Comience con un texto(cadena) y un patrón(cadena secundaria) para buscar.
2. Iterar a través del texto un carácter a la vez.
3. Para cada carácter del texto, compárelo con el primer carácter del patrón.
4. Si hay una coincidencia, verifique si los caracteres subsiguientes también coinciden con el patrón.
5. Si el patrón coincide completamente, registre la posición inicial del partido.
6. Continúe buscando el patrón en el texto.

Ejemplo

Considere un texto: "ababcababcabcabc" y un patrón: "abc"

1. Comience en la posición 0. Compare "a" con el primer carácter "a" en el patrón.
2. Coincidencia encontrada, pasar a los siguientes caracteres: "b" con "b" y "a" con "c".
3. Continúe emparejando: "b" con "a", "a" con "b" y "b" con "c".
4. Partido fallido en la posición 2.
5. Comience nuevamente en la posición 3. Compare "a" con el primer carácter "a" en el patrón.
6. Coincidencia exitosa: "a" con "a", "b" con "b" y "c" con "c".
7. Grabar posición 3.

El patrón "abc" se encuentra en las posiciones 0, 6 y 9.

Código de ejemplo en C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

En este ejemplo, la stringSearch función se usa para encontrar ocurrencias del patrón "abc" dentro del texto "ababcababcabcabc". El resultado será un vector que contiene las posiciones iniciales de los partidos.