Recherche de sous-chaîne en C++ : de la naïveté à la performance

Préface : Pourquoi « simplement find() » n'est pas toujours la réponse

Imaginez la situation : vous écrivez un analyseur de logs traitant des millions de lignes par seconde, ou un moteur de recherche textuelle. La première chose qui vient à l'esprit est d'appeler std::string::find(). « Ça marche ? Ça marche. Quoi de plus ? » — pense 90% des programmeurs. Et ils ont raison... jusqu'au moment où 10 millisecondes décident du sort de toute l'application.

La question « Check if a string contains a string in C++ » sur Stack Overflow a recueilli des centaines de milliers de vues. Et ce n'est pas un hasard. Cette tâche apparemment triviale cache de nombreux pièges : du choix de l'algorithme de recherche à l'utilisation correcte des fonctionnalités modernes de C++17 et C++20.

Dans cet article, nous ne montrerons pas seulement comment vérifier si une chaîne contient une sous-chaîne. Nous analyserons 7 façons de le faire, comparerons leurs performances sur des données réelles et donnerons des recommandations claires pour différents scénarios. C'est parti !

Le grand classique : std::string::find()

Commençons par les bases que tout le monde connaît. La méthode find() retourne la position de la première occurrence de la sous-chaîne ou la valeur spéciale std::string::npos si rien n'est trouvé.

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Bonjour, développeur C++ !";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "Sous-chaîne trouvée !" << std::endl;\n    }\n    \n    // Recherche avec une position de départ spécifiée\n    size_t pos = haystack.find("C++", 5); // commençons au 5ème caractère\n    return 0;\n}

Avantages : simplicité, lisibilité, intégré dans STL.
\nInconvénients : utilise un algorithme de recherche naïf (O(n*m) dans le pire des cas). Pour les chaînes courtes, c'est idéal ; pour les longues, cela peut ralentir.

Quand find() est-il un mal ?

Si vous recherchez une sous-chaîne dans une chaîne de 10⁵+ caractères, et que la sous-chaîne est longue et répétitive (par exemple, "aaaaaab" dans "aaaaaaaaaaaaaaaaaaaaab"), l'algorithme naïf commence à dégrader les performances. Dans de tels cas, find() peut être 10 à 100 fois plus lent que des alternatives optimisées.

string_view : légèreté et rapidité

Avec l'arrivée de C++17, nous avons std::string_view — une représentation non propriétaire d'une chaîne. Il est idéal pour les fonctions qui ne font que lire des données, sans les copier.

#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 = "L'optimisation en C++ est un art";\n    std::string_view pattern = "art";\n    \n    if (contains(text, pattern)) {\n        std::cout << "Trouvé !" << std::endl;\n    }\n    return 0;\n}

Pourquoi est-ce plus rapide ? Lors de la transmission d'un std::string à une fonction, une copie est effectuée (sauf si elle est passée par référence). string_view copie simplement le pointeur et la longueur — aucune allocation. Pour les appels fréquents de vérification de présence, cela offre un gain de performance allant jusqu'à 30–40%.

Mise à niveau algorithmique : Boyer-Moore et KMP

Si vous travaillez avec des données vraiment volumineuses, il est temps de se souvenir des algorithmes classiques de recherche de sous-chaîne. En C++17, les algorithmes de recherche de STL sont apparus :

\n
• std::boyer_moore_searcher — l'un des plus rapides pour les motifs longs
\n
• std::boyer_moore_horspool_searcher — version simplifiée, plus rapide sur les motifs courts
\n
• std::default_searcher — une enveloppe autour de la recherche naïve
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "Les algorithmes de recherche en C++ peuvent être très rapides";\n