Au programme de ce chapitre
- I. Le problème de la recherche d'un motif dans un texte
- II. Cas favorables et cas défavorables
- III. Applications de la recherche textuelle
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition La recherche de motif consiste à trouver toutes les positions où un motif (une courte chaîne de caractères) apparaît dans un texte plus long. On appelle n la longueur du texte et m la longueur du motif, avec m ≤ n.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3 :
>>> def recherche_motif(texte, motif):
... n = len(texte)
... m = len(motif)
... occurrences = []
... for i in range(n - m + 1):
... j = 0
... while j < m and texte[i + j] == motif[j]:
... j += 1
... if j == m:
... occurrences.append(i)
... return occurrences
...
>>> texte = "ANANAS_ET_BANANE_AU_CARAMEL"
>>> recherche_motif(texte, "ANA")
[0, 2, 11]while s'arrête dès la première lettre différente, ce qui évite de comparer inutilement toute la fin du motif quand la correspondance échoue tôt.Les erreurs fréquentes à éviter
Piège. L'approche naïve fonctionne mais peut être lente sur de grands textes : d'où les algorithmes optimisés.
L'astuce du prof
Astuce. Les algorithmes efficaces exploitent la structure du motif pour « sauter » des positions inutiles.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
En quoi consiste la recherche textuelle ?
Voir la correction
À chercher un motif (sous-chaîne) dans un texte, par exemple « ab » dans « cabane ».
Exercice 2
Quel est l'inconvénient de l'algorithme naïf ?
Voir la correction
Il peut faire beaucoup de comparaisons ; les algorithmes comme Boyer-Moore sont plus rapides.