Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
La recherche textuelle consiste à trouver les occurrences d'un motif (chaîne courte de longueur m) dans un texte (chaîne longue de longueur n). C'est une brique fondamentale des éditeurs de texte, moteurs de recherche et de la bio-informatique.
L'algorithme naïf aligne le motif à chaque position i du texte (de 0 à n-m) et compare caractère par caractère. En cas d'échec, on décale d'une seule position. Simple, mais coûteux : sa complexité dans le pire cas est O(n \times m), atteinte sur des chaînes très répétitives.
L'algorithme de Boyer-Moore accélère la recherche : il compare le motif de droite à gauche et, grâce à l'heuristique du mauvais caractère, peut sauter plusieurs positions d'un coup, ce qui le rend très efficace en pratique.
Complexité de l'algorithme naïf : T(n, m) = O(n \times m) \quad \text{(pire cas)}.
Algorithme naïf en Python :
def recherche_motif(texte, motif): n, m = len(texte), len(motif) positions = [] for i in range(n - m + 1): if texte[i:i+m] == motif: positions.append(i) return positions
# recherche_motif('xabcyabc', 'abc') -> [1, 5]
Principe Boyer-Moore (décalage sur échec) : aligner le caractère fautif du texte avec sa dernière occurrence dans le motif.
1. Bien repérer qui est le texte (long) et qui est le motif (court).
2. Pour l'algorithme naïf, parcourir i de 0 à n-m inclus (range(n-m+1)).
3. Comparer texte[i:i+m] au motif ou comparer caractère par caractère.
4. Collecter tous les indices de départ.
L'algorithme naïf et son analyse de complexité O(n \times m) sont systématiquement attendus ; l'algorithme de Boyer-Moore n'est exigible que par son principe (comparaison du motif de droite à gauche, saut de plusieurs positions grâce à l'heuristique du mauvais caractère), sans le code complet. Sachez écrire la recherche naïve et donner toutes les positions de départ d'un motif sur un exemple concret. À l'épreuve pratique, attention aux bornes de boucle (range(n - m + 1) pour ne pas dépasser la fin du texte) et aux chevauchements éventuels d'occurrences. Justifiez le pire cas en exhibant un texte et un motif très répétitifs, et soulignez que malgré ce pire cas, l'algorithme naïf reste rapide sur des textes ordinaires où les échecs surviennent tôt dans la comparaison.