String-Suchalgorithmus (String Search) in C++ – Erklärung, Beispiel und Code

Der String-Suchalgorithmus wird verwendet, um Vorkommen eines bestimmten Musters(Teilstring) innerhalb eines größeren Textes(String) zu finden. Dieser Algorithmus spielt eine entscheidende Rolle bei Textverarbeitungs-, Such- und Bearbeitungsaufgaben.

Wie es funktioniert

1. Beginnen Sie mit einem Text(String) und einem Muster(Teilstring), nach dem gesucht werden soll.
2. Durchlaufen Sie den Text Zeichen für Zeichen.
3. Vergleichen Sie jedes Zeichen im Text mit dem ersten Zeichen des Musters.
4. Wenn es eine Übereinstimmung gibt, prüfen Sie, ob die nachfolgenden Zeichen ebenfalls mit dem Muster übereinstimmen.
5. Wenn das Muster vollständig übereinstimmt, notieren Sie die Startposition der Übereinstimmung.
6. Suchen Sie weiter nach dem Muster im Text.

Beispiel

Betrachten Sie einen Text: „ababcababcabcabc“ und ein Muster: „abc“

1. Beginnen Sie bei Position 0. Vergleichen Sie „a“ mit dem ersten Zeichen „a“ im Muster.
2. Übereinstimmung gefunden, gehen Sie zu den nächsten Zeichen: „b“ mit „b“ und „a“ mit „c“.
3. Setzen Sie den Abgleich fort: „b“ mit „a“, „a“ mit „b“ und „b“ mit „c“.
4. Match scheiterte an Position 2.
5. Beginnen Sie erneut bei Position 3. Vergleichen Sie „a“ mit dem ersten Zeichen „a“ im Muster.
6. Erfolgreiche Übereinstimmung: „a“ mit „a“, „b“ mit „b“ und „c“ mit „c“.
7. Rekordplatz 3.

Das Muster „abc“ befindet sich an den Positionen 0, 6 und 9.

Beispielcode 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 diesem Beispiel stringSearch wird die Funktion verwendet, um Vorkommen des Musters „abc“ im Text „ababcababcabcabc“ zu finden. Das Ergebnis ist ein Vektor, der die Startpositionen der Übereinstimmungen enthält.