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.
