String-zoekalgoritme (String Search) in C ++- uitleg, voorbeeld en code

Het zoekalgoritme voor strings wordt gebruikt om exemplaren van een specifiek patroon(substring) binnen een grotere tekst(string) te vinden. Dit algoritme speelt een cruciale rol bij tekstverwerking, zoeken en manipulatietaken.

Hoe het werkt

1. Begin met een tekst(string) en een patroon(substring) om naar te zoeken.
2. Herhaal de tekst teken voor teken.
3. Vergelijk elk teken in de tekst met het eerste teken van het patroon.
4. Als er een overeenkomst is, controleer dan of de volgende tekens ook overeenkomen met het patroon.
5. Als het patroon volledig overeenkomt, noteer dan de startpositie van de wedstrijd.
6. Zoek verder naar het patroon in de tekst.

Voorbeeld

Beschouw een tekst: "ababcababcabcabc" En een patroon: "abc"

1. Begin bij positie 0. Vergelijk "a" met het eerste teken "a" in het patroon.
2. Overeenkomst gevonden, ga naar de volgende karakters: "b" met "b" en "a" met "c".
3. Ga door met matchen: "b" met "a", "a" met "b" en "b" met "c".
4. Wedstrijd mislukt op positie 2.
5. Begin opnieuw bij positie 3. Vergelijk "a" met het eerste teken "a" in het patroon.
6. Succesvolle match: "a" met "a", "b" met "b" en "c" met "c".
7. Noteer positie 3.

Het patroon "abc" is te vinden op de posities 0, 6 en 9.

Voorbeeldcode in 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;  
}  

In dit voorbeeld stringSearch wordt de functie gebruikt om exemplaren van het patroon "abc" in de tekst "ababcababcabcabc" te vinden. Het resultaat is een vector met daarin de startposities van de wedstrijden.