Textsuchalgorithmus (Text Search) in C++ – Erklärung, Beispiel und Code

Der Textsuchalgorithmus ist eine grundlegende Methode bei der Textverarbeitung und dem Informationsabruf. Mit diesem Algorithmus können wir das Vorkommen einer Teilzeichenfolge(oder eines Musters) in einem größeren Textstück lokalisieren und identifizieren.

Wie es funktioniert

1. Beginnen Sie mit einem größeren Textstück(oder Dokument) und einer Teilzeichenfolge, nach der gesucht werden soll.
2. Gehen Sie nacheinander jedes Zeichen des Textes durch.
3. Vergleichen Sie die Teilzeichenfolge mit einem Teil des Textes, der dieselbe Länge wie die Teilzeichenfolge hat. Wenn eine Übereinstimmung gefunden wird, notieren Sie die aktuelle Position.
4. Gehen Sie zur nächsten Position und setzen Sie den Vergleich fort.

Beispiel

Betrachten Sie den Text: „Suchen wir nach einem Teilstring in diesem Text, um zu sehen, wie der Algorithmus funktioniert.“

Und der Teilstring, nach dem gesucht werden soll: „substring“

1. Beginnen Sie bei Position 0. Vergleichen Sie Let' mit „substring“. Keine Übereinstimmung.
2. An Position 1 verschieben. et's Mit „Teilzeichenfolge“ vergleichen. Keine Übereinstimmung.
3. Gehen Sie zu Position 2. Vergleichen Sie t's „ mit „substring“. Keine Übereinstimmung.
4. Wechseln Sie zu Position 3. Vergleichen Sie 's s mit „Teilzeichenfolge“. Keine Übereinstimmung.
5. Gehen Sie zu Position 4. Vergleichen Sie se mit „Teilzeichenfolge“. Keine Übereinstimmung.
6. Gehen Sie zu Position 5. Vergleichen Sie sea mit „Teilzeichenfolge“. Keine Übereinstimmung.
7. Gehen Sie zu Position 6. Vergleichen Sie earc mit „Teilzeichenfolge“. Keine Übereinstimmung.
8. Gehen Sie zu Position 7. Vergleichen Sie arch mit „Teilzeichenfolge“. Keine Übereinstimmung.
9. Gehen Sie zu Position 8. Vergleichen Sie rch „ mit „substring“. Keine Übereinstimmung.
10. Gehen Sie zu Position 9. Vergleichen Sie ch w mit „Teilzeichenfolge“. Keine Übereinstimmung.
11. Gehen Sie zu Position 10. Vergleichen Sie h wi mit „Teilzeichenfolge“. Keine Übereinstimmung.
12. Gehen Sie zu Position 11. Vergleichen Sie „ wit mit „substring“. Keine Übereinstimmung.
13. Gehen Sie zu Position 12. Vergleichen Sie with mit „Teilzeichenfolge“. Keine Übereinstimmung.
14. Gehen Sie zu Position 13. Vergleichen Sie ithi mit „Teilzeichenfolge“. Keine Übereinstimmung.
15. Gehen Sie zu Position 14. Vergleichen Sie thin mit „Teilzeichenfolge“. Keine Übereinstimmung.
16. Gehen Sie zu Position 15. Vergleichen Sie hinn mit „Teilzeichenfolge“. Keine Übereinstimmung.
17. Gehen Sie zu Position 16. Vergleichen Sie in t mit „Teilzeichenfolge“. Keine Übereinstimmung.
18. Gehen Sie zu Position 17. Vergleichen Sie n th mit „substring“. Keine Übereinstimmung.
19. Gehen Sie zu Position 18. Vergleichen Sie „ thi mit „substring“. Keine Übereinstimmung.
20. Gehen Sie zu Position 19. Vergleichen Sie this mit „substring“. Keine Übereinstimmung.
21. Gehen Sie zu Position 20. Vergleichen Sie his „ mit „substring“. Keine Übereinstimmung.
22. Gehen Sie zu Position 21. Vergleichen Sie is t mit „Teilzeichenfolge“. Keine Übereinstimmung.
23. Gehen Sie zu Position 22. Vergleichen Sie s te  mit „Teilzeichenfolge“. Keine Übereinstimmung.
24. Gehen Sie zu Position 23. Vergleichen Sie ubst  mit „Teilzeichenfolge“. Keine Übereinstimmung.
25. Gehen Sie zu Position 24. Vergleichen Sie bstr mit „Teilzeichenfolge“. Keine Übereinstimmung.
26. Gehen Sie zu Position 25. Vergleichen Sie stre mit „Teilzeichenfolge“. Keine Übereinstimmung.
27. Gehen Sie zu Position 26. Vergleichen Sie trin  mit „Teilzeichenfolge“. Keine Übereinstimmung.
28. Gehen Sie zu Position 27. Vergleichen Sie ring  mit „substring“. Übereinstimmung gefunden, Rekordposition 27.

Der Teilstring „substring“ befindet sich an Position 27 im Text.

Beispielcode in C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

In diesem Beispiel textSearch wird die Funktion verwendet, um die Positionen des Teilstrings „substring“ innerhalb des Textes zu finden. Das Ergebnis ist ein Vektor, der die Startpositionen der Übereinstimmungen enthält.