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

O algoritmo de busca de string é usado para encontrar ocorrências de um padrão específico(substring) dentro de um texto maior(string). Esse algoritmo desempenha um papel crucial nas tarefas de processamento, pesquisa e manipulação de texto.

Como funciona

1. Comece com um texto(string) e um padrão(substring) para pesquisar.
2. Percorra o texto um caractere por vez.
3. Para cada caractere do texto, compare-o com o primeiro caractere do padrão.
4. Se houver correspondência, verifique se os caracteres subsequentes também correspondem ao padrão.
5. Se o padrão corresponder completamente, registre a posição inicial da correspondência.
6. Continue procurando o padrão no texto.

Exemplo

Considere um texto: "ababcababcabcabc" E um padrão: "abc"

1. Comece na posição 0. Compare "a" com o primeiro caractere "a" no padrão.
2. Correspondência encontrada, passe para os próximos caracteres: "b" com "b" e "a" com "c".
3. Continue combinando: "b" com "a", "a" com "b" e "b" com "c".
4. A correspondência falhou na posição 2.
5. Comece novamente na posição 3. Compare "a" com o primeiro caractere "a" no padrão.
6. Correspondência bem-sucedida: "a" com "a", "b" com "b" e "c" com "c".
7. Posição do registro 3.

O padrão "abc" é encontrado nas posições 0, 6 e 9.

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

Neste exemplo, a stringSearch função é utilizada para encontrar ocorrências do padrão "abc" dentro do texto "ababcababcabcabc". O resultado será um vetor contendo as posições iniciais das partidas.