close

Algorithme de recherche de texte (Text Search) en C++- Explication, exemple et code

L'algorithme de recherche de texte est une méthode fondamentale dans le traitement de texte et la recherche d'informations. Cet algorithme nous permet de localiser et d'identifier les occurrences d'une sous-chaîne(ou d'un modèle) dans un plus grand morceau de texte.

Comment ça fonctionne

  1. Commencez par un plus grand morceau de texte(ou document) et une sous-chaîne à rechercher.
  2. Parcourez chaque caractère du texte de manière séquentielle.
  3. Comparez la sous-chaîne avec une partie du texte qui a la même longueur que la sous-chaîne. Si une correspondance est trouvée, enregistrez la position actuelle.
  4. Passez à la position suivante et continuez la comparaison.

Exemple

Considérez le texte : "Recherchons une sous-chaîne dans ce texte pour voir comment l'algorithme fonctionne."

Et la sous-chaîne à rechercher : "sous-chaîne"

  1. Commencez à la position 0. Comparez Let' avec "sous-chaîne". Aucune concordance.
  2. Déplacez-vous en position 1. Comparez et's avec "sous-chaîne". Aucune concordance.
  3. Déplacez-vous en position 2. Comparez t's " avec "sous-chaîne". Aucune correspondance.
  4. Déplacez-vous en position 3. Comparez 's s avec "sous-chaîne". Aucune concordance.
  5. Déplacez-vous en position 4. Comparez se avec "sous-chaîne". Aucune concordance.
  6. Déplacez-vous en position 5. Comparez sea avec "sous-chaîne". Aucune concordance.
  7. Déplacez-vous en position 6. Comparez earc avec "sous-chaîne". Aucune concordance.
  8. Déplacez-vous en position 7. Comparez arch avec "sous-chaîne". Aucune concordance.
  9. Déplacez-vous en position 8. Comparez rch " avec " sous-chaîne ". Aucune correspondance.
  10. Déplacez-vous en position 9. Comparez ch w avec "sous-chaîne". Aucune concordance.
  11. Déplacez-vous en position 10. Comparez h wi avec "sous-chaîne". Aucune concordance.
  12. Déplacez-vous à la position 11. Comparez " wit avec " sous-chaîne ". Aucune correspondance.
  13. Déplacez-vous en position 12. Comparez with avec "sous-chaîne". Aucune concordance.
  14. Déplacez-vous à la position 13. Comparez ithi avec "sous-chaîne". Aucune concordance.
  15. Déplacez-vous à la position 14. Comparez thin avec "sous-chaîne". Aucune concordance.
  16. Déplacez-vous à la position 15. Comparez hinn avec "sous-chaîne". Aucune concordance.
  17. Déplacez-vous à la position 16. Comparez in t avec "sous-chaîne". Aucune concordance.
  18. Déplacez-vous à la position 17. Comparez n th avec "sous-chaîne". Aucune concordance.
  19. Déplacez-vous à la position 18. Comparez " thi avec " sous-chaîne ". Aucune correspondance.
  20. Déplacez-vous à la position 19. Comparez this avec "sous-chaîne". Aucune concordance.
  21. Déplacez-vous à la position 20. Comparez his " avec " sous-chaîne ". Aucune correspondance.
  22. Déplacez-vous à la position 21. Comparez is t avec "sous-chaîne". Aucune concordance.
  23. Déplacez-vous en position 22. Comparez s te  avec "sous-chaîne". Aucune concordance.
  24. Déplacez-vous à la position 23. Comparez ubst  avec "sous-chaîne". Aucune concordance.
  25. Déplacez-vous à la position 24. Comparez bstr avec "sous-chaîne". Aucune concordance.
  26. Déplacez-vous à la position 25. Comparez stre avec "sous-chaîne". Aucune concordance.
  27. Déplacez-vous à la position 26. Comparez trin  avec "sous-chaîne". Aucune concordance.
  28. Déplacez-vous à la position 27. Comparez ring  avec "sous-chaîne". Correspondance trouvée, position d'enregistrement 27.

La sous-chaîne "substring" se trouve à la position 27 dans le texte.

Exemple de code en 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;  
}

Dans cet exemple, la textSearch fonction est utilisée pour trouver les positions de la sous-chaîne "sous-chaîne" dans le texte. Le résultat sera un vecteur contenant les positions de départ des matchs.