Comment trouver toutes les occurrences d’un motif dans un texte ?

Réponse courte

Compare le motif avec chaque fenêtre de même longueur dans le texte, de gauche à droite. Enregistre chaque départ où tous les caractères correspondent, puis avance d’un indice pour conserver les occurrences qui se chevauchent.

Comprendre

Définir une occurrence

Une occurrence du motif à l’indice i signifie que le texte contient exactement les mêmes caractères de i à i + m − 1, où m est la longueur du motif. La recherche est sensible aux majuscules, espaces et accents si aucune règle de normalisation n’est prévue. Une occurrence peut apparaître au milieu d’un mot.

Parcourir les fenêtres

La méthode naïve essaie chaque départ possible du texte. À chaque position, elle compare les caractères un à un ; si tout le motif correspond, elle ajoute cet indice à la liste des résultats. On poursuit ensuite la recherche au départ suivant. Il faut examiner jusqu’au dernier départ possible inclus pour ne pas rater une occurrence qui finit exactement au dernier caractère.

Garder les chevauchements

Après une correspondance, avancer seulement d’un indice permet d’en trouver une autre qui partage des caractères avec la première. Dans ABABA, le motif ABA apparaît aux indices 0 et 2. Avancer directement de trois caractères après le premier résultat ferait manquer le second. Si le motif est plus long que le texte, aucune fenêtre n’existe ; le contrat doit aussi préciser la convention choisie pour un motif vide.

Étapes

  1. Calcule la longueur du texte n et celle du motif m.
  2. Essaie chaque départ de 0 jusqu’à n − m inclus, si m ne dépasse pas n.
  3. Compare les caractères du motif à la fenêtre du texte.
  4. Ajoute l’indice de départ si toute la fenêtre correspond, puis poursuis au départ suivant.

Exemples

  • Dans ABABA, le motif ABA apparaît aux positions 0 et 2 ; les deux occurrences partagent le caractère d’indice 2.
  • Dans la chaîne BANANE, le motif AN apparaît aux positions 1 et 3.
  • Le motif CHAT n’a aucune occurrence dans le texte SAC ; sa longueur dépasse celle du texte.

Pièges fréquents

  • Avancer de la longueur du motif après une réussite peut sauter une occurrence chevauchante, comme ABA aux indices 0 et 2 dans ABABA.
  • Ne chercher que des mots entiers ajoute une contrainte : une recherche de motif peut aussi trouver une suite de caractères à l’intérieur d’un mot.

Pourquoi ça marche

Tester chaque départ garantit de ne pas éliminer une position avant d’avoir comparé la fenêtre correspondante.

Et maintenant ?

Questions proches

← Toutes les questions-réponses