Substring Search in C++: From Naivety to Performance

Foreword: Why "just find()" is not always the answer

Imagine a scenario: you are writing a log parser processing millions of lines per second, or a text search engine. The first thing that comes to mind is to call std::string::find(). "It works? It works. What else do you need?" — thinks 90% of programmers. And they are right... until the moment when 10 milliseconds decide the fate of the entire application.

The question "Check if a string contains a string in C++" on Stack Overflow has gathered hundreds of thousands of views. And this is no coincidence. This seemingly trivial task hides many pitfalls: from choosing the search algorithm to correctly using modern C++17 and C++20 features.

In this article, we will not just show how to check if a string contains a substring. We will analyze 7 ways to do this, compare their performance on real data, and give clear recommendations for different scenarios. Let's go!

The Classic: std::string::find()

Let's start with the basics that everyone knows. The find() method returns the position of the first occurrence of the substring or the special value std::string::npos if nothing is found.

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Hello, C++ developer!";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "Substring found!" << std::endl;\n    }\n    \n    // Search with a specified starting position\n    size_t pos = haystack.find("C++", 5); // start from the 5th character\n    return 0;\n}

Pros: simplicity, readability, built into STL.
\nCons: uses a naive search algorithm (O(n*m) in the worst case). Ideal for short strings, but can be slow for long ones.

When is find() evil?

If you are searching for a substring in a string of length 10⁵+ characters, and the substring is long and repetitive (e.g., "aaaaaab" in "aaaaaaaaaaaaaaaaaaaaab"), the naive algorithm starts to degrade. In such cases, find() can be 10–100 times slower than optimized alternatives.

string_view: Lightweight and Fast

With the arrival of C++17, we got std::string_view — a non-owning view of a string. It is ideal for functions that only read data without copying it.

#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 = "Optimization in C++ is an art";\n    std::string_view pattern = "art";\n    \n    if (contains(text, pattern)) {\n        std::cout << "Found!" << std::endl;\n    }\n    return 0;\n}

Why is this faster? When passing a std::string to a function, copying occurs (if not passed by reference). string_view simply copies a pointer and a length — no allocations. For frequent contains checks, this gives a performance boost of up to 30–40%.

Algorithmic Upgrade: Boyer-Moore and KMP

If you are working with truly large data, it's time to remember the classic substring search algorithms. In C++17, STL search algorithms appeared:

\n
• std::boyer_moore_searcher — one of the fastest for long patterns
\n
• std::boyer_moore_horspool_searcher — a simplified version, faster on short patterns
\n
• std::default_searcher — a wrapper over naive search
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "Search algorithms in C++ can be very fast";\n