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

Strengesøkealgoritmen brukes til å finne forekomster av et spesifikt mønster(understreng) i en større tekst(streng). Denne algoritmen spiller en avgjørende rolle i tekstbehandling, søk og manipulasjonsoppgaver.

Hvordan det fungerer

1. Start med en tekst(streng) og et mønster(delstreng) å søke etter.
2. Iterér gjennom teksten ett tegn om gangen.
3. For hvert tegn i teksten, sammenligne det med det første tegnet i mønsteret.
4. Hvis det er samsvar, sjekk om de påfølgende tegnene også samsvarer med mønsteret.
5. Hvis mønsteret er helt samsvarende, noter startposisjonen til kampen.
6. Fortsett å søke etter mønsteret i teksten.

Eksempel

Tenk på en tekst: "ababcababcabcabc" og et mønster: "abc"

1. Start ved posisjon 0. Sammenlign "a" med det første tegnet "a" i mønsteret.
2. Samsvar funnet, gå til neste tegn: "b" med "b", og "a" med "c".
3. Fortsett å matche: "b" med "a", "a" med "b" og "b" med "c".
4. Kamp mislyktes på posisjon 2.
5. Start på nytt ved posisjon 3. Sammenlign "a" med det første tegnet "a" i mønsteret.
6. Vellykket samsvar: "a" med "a", "b" med "b" og "c" med "c".
7. Rekordposisjon 3.

Mønsteret "abc" finnes i posisjonene 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 eksemplet stringSearch brukes funksjonen til å finne forekomster av mønsteret "abc" i teksten "ababcababcabcabc". Resultatet vil være en vektor som inneholder startposisjonene til kampene.