NSI · Terminale · Algorithmique
Recherche de sous-chaîne
Retrouver un motif sans tout relire.
En bref
Chercher un motif de longueur m dans un texte de longueur n est l’opération la plus fréquente de l’informatique : chaque recherche dans un document, chaque filtre, chaque analyse de séquence génétique la met en jeu.
Les trois algorithmes
| Algorithme | Son coût | Son idée |
|---|---|---|
| Naïf | jusqu’à m × n | Décaler d’un cran à chaque échec |
| Boyer-Moore-Horspool | m × n en pire cas, très rapide en pratique | Comparer de droite à gauche, sauter d’un bloc |
| Knuth-Morris-Pratt | n + m, garanti | Ne jamais revenir en arrière dans le texte |
L’algorithme naïf
On aligne le motif sur la première position, on compare caractère par caractère, et au moindre désaccord on décale d’un cran en repartant du début du motif.
| Avantage | Pire cas |
|---|---|
| Aucun prétraitement, cinq lignes de code | Un texte fait d’une lettre répétée et un motif presque identique : chaque alignement va presque au bout avant d’échouer |
Ce qu’il gaspille : à chaque échec, il oublie tout ce qu’il vient d’apprendre. Or les caractères déjà comparés renseignent — certains décalages sont impossibles.
Boyer-Moore-Horspool
| Idée | Ce qu’elle permet |
|---|---|
| Comparer le motif de droite à gauche | L’échec survient plus tôt |
| Une table de décalage calculée sur le motif | En cas d’échec, on décale d’après le caractère fautif du texte |
Si ce caractère n’apparaît pas dans le motif, on décale d’un coup de la longueur entière du motif : des positions sont écartées sans jamais être examinées. D’où sa rapidité sur du texte naturel — d’autant plus grande que le motif est long.
Knuth-Morris-Pratt
Il précalcule, pour chaque préfixe du motif, la longueur du plus long préfixe qui est aussi un suffixe. Cette table permet, en cas d’échec, de reprendre au bon endroit sans jamais reculer dans le texte.
Coût n + m dans tous les cas : linéaire, garanti.
Le prétraitement
Les deux algorithmes efficaces partagent le même principe : investir un calcul sur le motif — en m opérations — pour économiser ensuite sur le texte. Rentable dès que le texte est bien plus long que le motif, ce qui est le cas usuel.
Choisir
| La situation | L’algorithme |
|---|---|
| Motif court, texte court, code à écrire vite | Le naïf |
| Texte naturel, motif long, recherche unique | Boyer-Moore |
| Garantie de performance, motif très répétitif | Knuth-Morris-Pratt |
| Recherches nombreuses dans un texte fixe | Construire un index une fois pour toutes |
Le fil commun de tout le chapitre d’algorithmique : ne pas refaire ce qui a déjà été fait. Diviser pour régner évite de tout examiner, la programmation dynamique évite de recalculer, la recherche de motif évite de recomparer.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quel est le coût de l’algorithme naïf de recherche de sous-chaîne dans le pire cas ?
2.Dans quel sens l’algorithme de Boyer-Moore compare-t-il le motif ?
3.De combien peut-on décaler en Boyer-Moore quand le caractère fautif n’apparaît pas dans le motif ?
4.Quel est le coût garanti de l’algorithme de Knuth-Morris-Pratt ?
5.Que précalcule Knuth-Morris-Pratt ?
6.Le prétraitement du motif n’est rentable que si le texte est bien plus long que le motif.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Recherche de motif » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
