Retour au cours

Leçon 56 : Algorithmes de String Matching : Introduction à l'Approche Naïve

Algorithmes : De Zéro à Héro (Un Guide pour Débutants)

56. Algorithmes de String Matching (Recherche de Chaînes) : Introduction à l'Approche Naïve

Le string matching est le problème de la recherche des occurrences d'une chaîne 'pattern' P dans une chaîne 'text' T plus grande.

L'Algorithme Naïf

L'approche la plus simple est la méthode par force brute, où nous vérifions chaque position possible dans le texte où le pattern pourrait commencer.

  1. Commencer à l'index i = 0 dans le Text T.
  2. Comparer le Pattern P (de longueur M) caractère par caractère avec la sous-chaîne de T commençant à i.
  3. Si tous les caractères correspondent, une correspondance est trouvée.
  4. Si un décalage se produit, décaler le pattern d'une position (incrémenter i) et recommencer la comparaison.

Efficacité

Si la longueur du Text est N et la longueur du Pattern est M :

  • Temps du Pire Cas : O(N * M).
    • Cela se produit si le pattern et le texte correspondent presque à chaque position (par exemple, Text = 'AAAAAB', Pattern = 'AAAB'). L'algorithme effectue près de M comparaisons N fois.

Pour un string matching pratique et plus rapide, des algorithmes plus avancés comme KMP ou Rabin-Karp sont nécessaires.