Pesquisa de substring em C++: da ingenuidade ao desempenho

Prefácio: Por que "apenas find()" nem sempre é a resposta

Imagine a situação: você está escrevendo um parser de logs, processando milhões de linhas por segundo, ou um mecanismo de busca de texto. A primeira coisa que vem à mente é chamar std::string::find(). "Funciona? Funciona. O que mais é necessário?" — pensam 90% dos programadores. E eles estão certos... até o momento em que 10 milissegundos decidem o destino de toda a aplicação.

A pergunta "Check if a string contains a string in C++" no Stack Overflow acumulou centenas de milhares de visualizações. E isso não é por acaso. Uma tarefa aparentemente trivial esconde muitas armadilhas: desde a escolha do algoritmo de busca até o uso correto dos recursos modernos do C++17 e C++20.

Neste artigo, não vamos apenas mostrar como verificar se uma string contém uma substring. Vamos analisar 7 maneiras de fazer isso, comparar seu desempenho em dados reais e dar recomendações claras para diferentes cenários. Vamos nessa!

Clássico do gênero: std::string::find()

Vamos começar com o básico que todo mundo conhece. O método find() retorna a posição da primeira ocorrência da substring ou o valor especial std::string::npos se nada for encontrado.

#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 encontrada!" << std::endl;\n    }\n    \n    // Busca com posição inicial especificada\n    size_t pos = haystack.find("C++", 5); // começaremos a partir do 5º caractere\n    return 0;\n}

Vantagens: simplicidade, legibilidade, embutido no STL.
\nDesvantagens: usa algoritmo de busca ingênuo (O(n*m) no pior caso). Para strings curtas é ideal, para strings longas pode ser lento.

Quando find() é o vilão?

Se você está procurando uma substring em uma string de comprimento 10⁵+ caracteres, e a substring é longa e repetitiva (por exemplo, "aaaaaab" em "aaaaaaaaaaaaaaaaaaaaab"), o algoritmo ingênuo começa a degradar. Nesses casos, find() pode ser de 10 a 100 vezes mais lento que alternativas otimizadas.

string_view: leveza e velocidade

Com a chegada do C++17, ganhamos std::string_view — uma representação não proprietária de string. É ideal para funções que apenas leem dados, sem copiá-los.

#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 = "Otimização em C++ é uma arte";\n    std::string_view pattern = "arte";\n    \n    if (contains(text, pattern)) {\n        std::cout << "Encontrado!" << std::endl;\n    }\n    return 0;\n}

Por que é mais rápido? Ao passar std::string para uma função, ocorre cópia (se não for passada por referência). string_view simplesmente copia o ponteiro e o comprimento — sem alocações. Para chamadas frequentes de verificação de ocorrência, isso proporciona um ganho de desempenho de até 30–40%.

Upgrade algorítmico: Boyer-Moore e KMP

Se você trabalha com dados realmente grandes, é hora de lembrar dos algoritmos clássicos de busca de substring. No C++17, surgiram os algoritmos de busca do STL:

\n
• std::boyer_moore_searcher — um dos mais rápidos para padrões longos
\n
• std::boyer_moore_horspool_searcher — versão simplificada, mais rápida em padrões curtos
\n
• std::default_searcher — wrapper sobre a busca ingênua
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "Algoritmos de busca em C++ podem ser muito rápidos";\n