Algorithme de recherche de chaînes (String Search) en C++- Explication, exemple et code

L'algorithme de recherche de chaîne est utilisé pour trouver des occurrences d'un modèle spécifique(sous-chaîne) dans un texte plus long(chaîne). Cet algorithme joue un rôle crucial dans les tâches de traitement, de recherche et de manipulation de texte.

Comment ça fonctionne

1. Commencez par un texte(chaîne) et un modèle(sous-chaîne) à rechercher.
2. Parcourez le texte un caractère à la fois.
3. Pour chaque caractère du texte, comparez-le avec le premier caractère du motif.
4. S'il y a une correspondance, vérifiez si les caractères suivants correspondent également au modèle.
5. Si le modèle est complètement assorti, enregistrez la position de départ du match.
6. Continuez à chercher le motif dans le texte.

Exemple

Considérez un texte: « ababcababcabcabc » et un motif: « abc »

1. Commencez à la position 0. Comparez "a" avec le premier caractère "a" du motif.
2. Correspondance trouvée, passez aux caractères suivants : "b" avec "b" et "a" avec "c".
3. Continuez à faire correspondre : "b" avec "a", "a" avec "b" et "b" avec "c".
4. Le match a échoué à la position 2.
5. Recommencez à la position 3. Comparez "a" avec le premier caractère "a" du motif.
6. Correspondance réussie : "a" avec "a", "b" avec "b" et "c" avec "c".
7. Position d'enregistrement 3.

Le motif "abc" se trouve aux positions 0, 6 et 9.

Exemple de code en C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Dans cet exemple, la stringSearch fonction est utilisée pour trouver des occurrences du modèle "abc" dans le texte "ababcababcabcabc". Le résultat sera un vecteur contenant les positions de départ des matchs.