Teilstringsuche in C++: Von der Naivität zur Leistung

Vorwort: Warum „einfach find()“ nicht immer die Antwort ist

Stellen Sie sich vor: Sie schreiben einen Log-Parser, der Millionen von Zeilen pro Sekunde verarbeitet, oder eine Textsuchmaschine. Das Erste, was einem in den Sinn kommt, ist der Aufruf von std::string::find(). „Funktioniert es? Funktioniert es. Was braucht man mehr?“, denken 90% der Programmierer. Und sie haben recht... bis der Moment kommt, in dem 10 Millisekunden über das Schicksal der gesamten Anwendung entscheiden.

Die Frage „Check if a string contains a string in C++“ auf Stack Overflow hat Hunderttausende von Aufrufen gesammelt. Und das ist kein Zufall. Die scheinbar triviale Aufgabe birgt viele Fallstricke: von der Wahl des Suchalgorithmus bis zur korrekten Verwendung moderner C++17- und C++20-Funktionen.

In diesem Artikel zeigen wir nicht nur, wie man überprüft, ob ein String einen Teilstring enthält. Wir analysieren 7 Methoden, vergleichen ihre Leistung mit echten Daten und geben klare Empfehlungen für verschiedene Szenarien. Los geht's!

Der Klassiker: std::string::find()

Beginnen wir mit der Basis, die jeder kennt. Die Methode find() gibt die Position des ersten Vorkommens des Teilstrings oder den speziellen Wert std::string::npos zurück, wenn nichts gefunden wurde.

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Hallo, C++ Entwickler!";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "Teilstring gefunden!" << std::endl;\n    }\n    \n    // Suche mit Angabe der Startposition\n    size_t pos = haystack.find("C++", 5); // beginne beim 5. Zeichen\n    return 0;\n}

Vorteile: Einfachheit, Lesbarkeit, in STL integriert.
\nNachteile: Verwendet einen naiven Suchalgorithmus (O(n*m) im schlechtesten Fall). Für kurze Strings ideal, für lange kann es langsam werden.

Wann ist find() schlecht?

Wenn Sie einen Teilstring in einem String mit einer Länge von 10⁵+ Zeichen suchen und der Teilstring lang und sich wiederholend ist (z. B. "aaaaaab" in "aaaaaaaaaaaaaaaaaaaaab"), beginnt der naive Algorithmus zu degradieren. In solchen Fällen kann find() 10–100 Mal langsamer sein als optimierte Alternativen.

string_view: Leichtigkeit und Geschwindigkeit

Mit C++17 haben wir std::string_view bekommen – eine nicht-besitzende Darstellung eines Strings. Es ist ideal für Funktionen, die nur Daten lesen, ohne sie zu kopieren.

#include <iostream>\n#include <string_view>\n\nbool contains(std::string_view haystack, std::string_view needle) {\n    return haystack.find(needle) != std::string_view::npos;\n}\n\nint main() {\n    std::string_view text = "Optimierung in C++ ist eine Kunst";\n    std::string_view pattern = "Kunst";\n    \n    if (contains(text, pattern)) {\n        std::cout << "Gefunden!" << std::endl;\n    }\n    return 0;\n}

Warum ist das schneller? Bei der Übergabe von std::string an eine Funktion erfolgt eine Kopie (wenn nicht per Referenz übergeben). string_view kopiert einfach den Zeiger und die Länge – keine Allokationen. Bei häufigen Aufrufen zur Überprüfung auf Enthaltensein ergibt sich ein Leistungsgewinn von bis zu 30–40%.

Algorithmisches Upgrade: Boyer-Moore und KMP

Wenn Sie mit wirklich großen Datenmengen arbeiten, ist es an der Zeit, sich an die klassischen Teilstring-Suchalgorithmen zu erinnern. In C++17 gibt es Suchalgorithmen aus der STL:

\n
• std::boyer_moore_searcher – einer der schnellsten für lange Muster
\n
• std::boyer_moore_horspool_searcher – vereinfachte Version, schneller bei kurzen Mustern
\n
• std::default_searcher – ein Wrapper um die naive Suche
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "Suchalgorithmen in C++ können sehr schnell sein";\n