Informatique · Terminale · 2 min de lecture
Comprendre le décalage du mauvais caractère
Rechercher un motif dans un texte : l'algorithme naïf compare le motif à chaque position ; l'algorithme de Boyer-Moore compare le motif de droite à gauche et, grâce à un prétraitement du motif (table de la dernière position de chaque caractère dans le motif), décale le motif de plusieurs positions en cas de non-correspondance.
Chapitre du programme : Numérique et sciences informatiques (spécialité)
Bloc 1 sur 7 · Comprendre
Comprendre
La recherche de Boyer-Moore compare un motif au texte en parcourant le motif de droite à gauche. Lors d'un désaccord, des informations sur le motif permettent de décaler l'alignement et d'éviter certaines comparaisons inutiles. Plusieurs heuristiques existent ; la règle du mauvais caractère est l'une d'elles.
Bloc 2 sur 7 · Approfondir
Approfondir
Avec des indices commençant à zéro, notez j la position du désaccord dans le motif et last(c) la dernière occurrence du caractère du texte c dans le motif. Dans la version simplifiée étudiée ici, le décalage est le maximum de1 et j−last(c), avec last(c)=−1 si c est absent.
Bloc 3 sur 7 · Exemple
Exemple travaillé
Pour le motif ABCA, un désaccord à l'indice3 avec un B dans le texte donne last(B)=1. Le décalage de la règle étudiée vaut max(1,3−1)=2. Si le mauvais caractère est Z, absent du motif, on obtient max(1,3−(−1))=4. Le choix du caractère du texte en désaccord est donc décisif.
Bloc 4 sur 7 · Visualiser
Visualiser le raisonnement
Écrivez ABCA avec les indices0,1,2,3. Sous la position3, placez le caractère en désaccord du texte. Déplacez ensuite le motif pour aligner sa dernière occurrence de ce caractère avec cette position, lorsque l'alignement donne un déplacement positif.
Continuez sur votre lancée
Vous avez découvert l’essentiel et un exemple. Retrouvez la suite du cours et les points à retenir, puis passez à l’entraînement guidé dans votre compte.
- Les formules et les repères à retenir
- Les erreurs fréquentes expliquées
- Un exercice avec des aides et sa correction
L’accès gratuit comprend les cours et exercices de votre niveau choisi.
Sources
- Boyer et Moore, article original : https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
- Princeton, recherche de sous-chaînes : https://algs4.cs.princeton.edu/53substring/
Vous pensez avoir trouvé une erreur dans cette leçon ? Signalez-la par e-mail.