Rechercher dans un texte

Appelons texte la chaîne dans laquelle on cherche, motif la chaîne cherchée, n la longueur du texte et m celle du motif. Une occurrence à l’indice i signifie que les m caractères texte[i], …, texte[i + m − 1] sont respectivement égaux aux caractères du motif. Le dernier départ possible est n − m, inclus. Si m dépasse n, il n’existe aucun départ possible.

Le résultat peut être un booléen, l’indice de la première occurrence, ou la liste de toutes les occurrences. Ces contrats sont différents. Ici, on cherche d’abord la première occurrence et on renvoie −1 en cas d’absence. Pour un motif vide, nous choisissons explicitement la convention de renvoyer zéro. L’algorithme de décalage sera ensuite décrit pour un motif non vide.

La recherche exacte distingue les majuscules, les minuscules, les espaces et les accents. Chercher CHAT n’est pas chercher chat ni seulement un mot entier : un motif peut apparaître à l’intérieur d’un mot plus long. Un traitement qui ignore la casse ou limite les résultats aux mots entiers ajoute d’autres règles. Il faut les spécifier avant de choisir les tests, et garder la correspondance entre les indices si l’on transforme le texte.

La méthode naïve essaie chaque départ de gauche à droite. Pour chaque fenêtre, elle compare les caractères du motif et du texte jusqu’à une différence ou jusqu’à la correspondance complète. Après un échec, elle avance d’une position. Elle est simple, mais elle répète parfois beaucoup de comparaisons. La borne évidente est m × (n − m + 1) comparaisons lorsque 1 ≤ m ≤ n.

Boyer–Moore exploite l’information obtenue pendant une comparaison pour éviter certains départs impossibles. La famille contient plusieurs variantes. La version présentée ici, dite de Horspool, utilise une table de décalages et le caractère du texte placé à l’extrémité droite de la fenêtre. Elle ne mélange pas cette règle avec celle du caractère rencontré à un autre endroit lors de l’échec.

Dans une fenêtre fixée, on compare le motif de droite à gauche. Le départ de la fenêtre, lui, progresse toujours vers la droite du texte. Le sens des comparaisons et le sens de déplacement sont donc deux notions distinctes. Si toutes les lettres correspondent, on a trouvé une occurrence. Sinon, la table indique de combien avancer la fenêtre, sans recommencer automatiquement au départ suivant.

Pour le motif CHAT de longueur quatre, la dernière case est T. On construit la table à partir de toutes les autres positions. C est à trois places du bord droit, H à deux places et A à une place. Tout caractère absent de cette partie du motif reçoit le décalage quatre. La table est donc C : 3 ; H : 2 ; A : 1 ; autres caractères : 4, y compris T dans ce motif.

Pourquoi exclure la dernière case du motif ? Sa distance au bord droit est zéro. L’utiliser créerait un décalage nul pour ce caractère et pourrait bloquer la progression. En excluant cette case, tous les décalages construits sont strictement positifs. La recherche avance donc et finit par dépasser le dernier départ possible si elle ne trouve pas de correspondance.

Le décalage est sûr car le caractère placé au bord droit doit être aligné avec une occurrence compatible dans le motif si une nouvelle correspondance le recouvre. On choisit l’occurrence la plus à droite avant la dernière case. Les décalages plus petits aligneraient ce caractère avec des positions où il est absent. S’il n’apparaît nulle part dans cette partie, on peut avancer de m positions. Cette explication concerne cette variante précise, pas n’importe quelle formule de saut.

Pour programmer, garder deux indices de rôles différents : i repère le début de la fenêtre dans le texte, j repère la position comparée dans le motif. À chaque nouvelle fenêtre, remettre j à m − 1. Tant que j est positif ou nul et que les deux caractères correspondent, diminuer j. Lorsque j devient négatif, la correspondance est complète. Sinon, augmenter i selon la table avant de recommencer.

La condition de boucle sur les fenêtres est i + m ≤ n. Elle autorise une occurrence qui se termine exactement au dernier caractère du texte. Le test j ≥ 0 doit précéder l’accès aux caractères pour ne pas laisser les indices négatifs de Python comparer involontairement la fin des chaînes. Une trace écrite montre rapidement ces erreurs de frontière.

Les tests doivent inclure un motif absent, un motif plus long que le texte, une occurrence au début, une à la fin, des lettres répétées et un texte vide. Pour la convention du motif vide, vérifier explicitement le résultat zéro. Sur de petites chaînes, on peut comparer systématiquement sa fonction à une recherche naïve indépendante ou à str.find. Une égalité sur beaucoup de cas détecte des erreurs ; la sûreté des sauts reste expliquée par le raisonnement.

Le prétraitement se fait une fois par motif, puis sert à toutes les fenêtres de la recherche. Son intérêt augmente lorsqu’un même motif est cherché dans de grands textes. On ne prétend pas que cette méthode est toujours plus rapide pour toutes les entrées. Le programme de terminale privilégie la compréhension des comparaisons et du prétraitement ; une analyse complète du coût de Boyer–Moore n’est pas exigée.

Pour poursuivre ton entraînement, ouvre la rubrique S’entraîner du site, à l’adresse /exercices. Reprends d’abord les questions de cette leçon sans afficher les réponses, puis compare ton raisonnement à la correction.