String Search (String Search) Algoritme i C++- Forklaring, Eksempel og Kode

Strengsøgningsalgoritmen bruges til at finde forekomster af et specifikt mønster(understreng) i en større tekst(streng). Denne algoritme spiller en afgørende rolle i tekstbehandlings-, søgnings- og manipulationsopgaver.

Hvordan det virker

1. Start med en tekst(streng) og et mønster(understreng) at søge efter.
2. Gentag teksten et tegn ad gangen.
3. For hvert tegn i teksten skal du sammenligne det med det første tegn i mønsteret.
4. Hvis der er et match, så tjek om de efterfølgende tegn også matcher mønsteret.
5. Hvis mønsteret er helt matchet, skal du registrere kampens startposition.
6. Fortsæt med at søge efter mønsteret i teksten.

Eksempel

Overvej en tekst: "ababcababcabcabc" Og et mønster: "abc"

1. Start ved position 0. Sammenlign "a" med det første tegn "a" i mønsteret.
2. Match fundet, flyt til de næste tegn: "b" med "b", og "a" med "c".
3. Fortsæt med at matche: "b" med "a", "a" med "b" og "b" med "c".
4. Kamp mislykkedes på position 2.
5. Start igen ved position 3. Sammenlign "a" med det første tegn "a" i mønsteret.
6. Vellykket match: "a" med "a", "b" med "b" og "c" med "c".
7. Optag position 3.

Mønsteret "abc" findes på positionerne 0, 6 og 9.

Eksempelkode i 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;  
}  

I dette eksempel stringSearch bruges funktionen til at finde forekomster af mønsteret "abc" i teksten "ababcababcabcabc". Resultatet vil være en vektor, der indeholder startpositionerne for kampene.