Comment déterminer la dernière position possible d’un motif dans un texte ?

Réponse courte

Si le texte a n caractères et le motif m caractères, son dernier indice de départ possible est n − m, inclus, à condition que m ≤ n. Si m > n, le motif ne peut commencer nulle part.

Comprendre

Raisonner avec les indices

En Python, les indices d’un texte de longueur n vont de 0 à n − 1. Un motif de longueur m posé à l’indice i occupe les indices i à i + m − 1. Pour rester dans le texte, le dernier indice occupé doit être au plus n − 1. Donc i + m − 1 ≤ n − 1, ce qui donne i ≤ n − m.

Inclure la dernière fenêtre

La position n − m est un départ valide : le motif se termine alors exactement sur le dernier caractère du texte. Pour parcourir toutes les fenêtres, la condition peut s’écrire i + m ≤ n. En revanche, si on utilise une borne supérieure exclusive dans range, il faut écrire range(n − m + 1) afin d’inclure le départ n − m.

Vérifier les tailles

Cette formule suppose que le motif n’est pas plus long que le texte. Si m > n, alors n − m est négatif et aucune fenêtre complète ne peut être comparée. Le cas du motif vide dépend de la convention choisie pour la fonction.

Exemples

  • Un texte de 10 caractères et un motif de 4 caractères donnent un dernier départ possible à l’indice 6 ; la fenêtre occupe les indices 6 à 9.
  • Pour texte = CHAT et motif = CHAT, n = m = 4 : le seul départ possible est 0.
  • Si le texte compte 3 caractères et le motif 5, il n’existe aucun départ possible.

Pièges fréquents

  • Écrire range(n − m) oublie la position n − m, alors qu’elle permet une fenêtre finissant sur le dernier caractère.
  • Confondre dernier indice et nombre de positions conduit à ajouter ou retirer un caractère ; les indices commencent à zéro, mais le nombre de départs possibles est n − m + 1.

Pourquoi ça marche

Le motif tient dans le texte tant que son dernier indice, i + m − 1, ne dépasse pas le dernier indice du texte, n − 1.

Et maintenant ?

Questions proches

← Toutes les questions-réponses