Algoritmo de Pesquisa de Texto (Text Search) em C++- Explicação, Exemplo e Código

O algoritmo Text Search é um método fundamental no processamento de texto e recuperação de informações. Esse algoritmo nos permite localizar e identificar ocorrências de uma substring(ou padrão) em um trecho maior de texto.

Como funciona

1. Comece com um pedaço maior de texto(ou documento) e uma substring para pesquisar.
2. Percorra cada caractere do texto sequencialmente.
3. Compare a substring com uma parte do texto que tem o mesmo comprimento que a substring. Se for encontrada uma correspondência, registre a posição atual.
4. Mova para a próxima posição e continue a comparação.

Exemplo

Considere o texto: "Vamos procurar uma substring neste texto para ver como o algoritmo funciona."

E a substring a ser pesquisada: "substring"

1. Comece na posição 0. Compare Let' com "substring". Nenhuma correspondência.
2. Mover para a posição 1. Compare et's com "substring". Nenhuma partida.
3. Mover para a posição 2. Compare t's " com "substring". Nenhuma correspondência.
4. Mover para a posição 3. Compare 's s com "substring". Nenhuma partida.
5. Mover para a posição 4. Compare se com "substring". Nenhuma partida.
6. Mover para a posição 5. Compare sea com "substring". Nenhuma correspondência.
7. Mover para a posição 6. Compare earc com "substring". Nenhuma partida.
8. Mover para a posição 7. Compare arch com "substring". Nenhuma correspondência.
9. Mover para a posição 8. Compare rch " com "substring". Nenhuma correspondência.
10. Mover para a posição 9. Compare ch w com "substring". Nenhuma correspondência.
11. Mover para a posição 10. Compare h wi com "substring". Nenhuma correspondência.
12. Mover para a posição 11. Compare " wit com "substring". Nenhuma correspondência.
13. Mover para a posição 12. Compare with com "substring". Nenhuma correspondência.
14. Mover para a posição 13. Compare ithi com "substring". Nenhuma partida.
15. Mover para a posição 14. Compare thin com "substring". Nenhuma partida.
16. Mover para a posição 15. Compare hinn com "substring". Nenhuma correspondência.
17. Mover para a posição 16. Compare in t com "substring". Nenhuma partida.
18. Mover para a posição 17. Compare n th com "substring". Nenhuma correspondência.
19. Mover para a posição 18. Compare " thi com "substring". Nenhuma correspondência.
20. Mover para a posição 19. Compare this com "substring". Nenhuma correspondência.
21. Mover para a posição 20. Compare his " com "substring". Nenhuma correspondência.
22. Mover para a posição 21. Compare is t com "substring". Nenhuma correspondência.
23. Mover para a posição 22. Compare s te  com "substring". Nenhuma partida.
24. Mover para a posição 23. Compare ubst  com "substring". Nenhuma correspondência.
25. Mover para a posição 24. Compare bstr com "substring". Nenhuma correspondência.
26. Mover para a posição 25. Compare stre com "substring". Nenhuma correspondência.
27. Mover para a posição 26. Compare trin  com "substring". Nenhuma correspondência.
28. Mover para a posição 27. Compare ring  com "substring". Correspondência encontrada, posição de registro 27.

A substring "substring" é encontrada na posição 27 dentro do texto.

Exemplo de código em 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;  
}  

Neste exemplo, a textSearch função é usada para encontrar as posições da substring "substring" dentro do texto. O resultado será um vetor contendo as posições iniciais das partidas.