close

Algoritmo de búsqueda de texto (Text Search) en C++- Explicación, ejemplo y código

El algoritmo de búsqueda de texto es un método fundamental en el procesamiento de texto y la recuperación de información. Este algoritmo nos permite ubicar e identificar ocurrencias de una subcadena(o patrón) dentro de un texto más grande.

Cómo funciona

  1. Comience con un fragmento de texto(o documento) más grande y una subcadena para buscar.
  2. Iterar a través de cada carácter del texto secuencialmente.
  3. Compare la subcadena con una parte del texto que tenga la misma longitud que la subcadena. Si se encuentra una coincidencia, registre la posición actual.
  4. Muévase a la siguiente posición y continúe la comparación.

Ejemplo

Considere el texto: "Busquemos una subcadena dentro de este texto para ver cómo funciona el algoritmo".

Y la subcadena a buscar: "subcadena"

  1. Comience en la posición 0. Compare Let' con "subcadena". Sin coincidencia.
  2. Mover a la posición 1. Comparar et's con "subcadena". Sin coincidencia.
  3. Mover a la posición 2. Comparar t's " con "subcadena". No hay coincidencia.
  4. Mover a la posición 3. Comparar 's s con "subcadena". Sin coincidencia.
  5. Mover a la posición 4. Comparar se con "subcadena". Sin coincidencia.
  6. Mover a la posición 5. Comparar sea con "subcadena". Sin coincidencia.
  7. Mover a la posición 6. Comparar earc con "subcadena". Sin coincidencia.
  8. Mover a la posición 7. Comparar arch con "subcadena". Sin coincidencia.
  9. Mover a la posición 8. Comparar rch " con "subcadena". No hay coincidencia.
  10. Mover a la posición 9. Comparar ch w con "subcadena". Sin coincidencia.
  11. Mover a la posición 10. Comparar h wi con "subcadena". Sin coincidencia.
  12. Mover a la posición 11. Comparar " wit con "subcadena". No hay coincidencia.
  13. Mover a la posición 12. Comparar with con "subcadena". Sin coincidencia.
  14. Mover a la posición 13. Comparar ithi con "subcadena". Sin coincidencia.
  15. Mover a la posición 14. Comparar thin con "subcadena". Sin coincidencia.
  16. Mover a la posición 15. Comparar hinn con "subcadena". Sin coincidencia.
  17. Mover a la posición 16. Comparar in t con "subcadena". Sin coincidencia.
  18. Mover a la posición 17. Comparar n th con "subcadena". Sin coincidencia.
  19. Mover a la posición 18. Comparar " thi con "subcadena". No hay coincidencia.
  20. Mover a la posición 19. Comparar this con "subcadena". Sin coincidencia.
  21. Mover a la posición 20. Comparar his " con "subcadena". No hay coincidencia.
  22. Mover a la posición 21. Comparar is t con "subcadena". Sin coincidencia.
  23. Mover a la posición 22. Comparar s te  con "subcadena". Sin coincidencia.
  24. Mover a la posición 23. Comparar ubst  con "subcadena". Sin coincidencia.
  25. Mover a la posición 24. Comparar bstr con "subcadena". Sin coincidencia.
  26. Mover a la posición 25. Comparar stre con "subcadena". Sin coincidencia.
  27. Mover a la posición 26. Comparar trin  con "subcadena". Sin coincidencia.
  28. Mover a la posición 27. Comparar ring  con "subcadena". Coincidencia encontrada, posición de registro 27.

La subcadena "subcadena" se encuentra en la posición 27 dentro del texto.

Código de ejemplo en C++ 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

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