Informatique · Terminale · 1 exercice vérifié
S’entraîner : Recherche textuelle : algorithme de Boyer-Moore
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Rechercher un motif dans un texte : l'algorithme naïf compare le motif à chaque position ; l'algorithme de Boyer-Moore compare le motif de droite à gauche et, grâce à un prétraitement du motif (table de la dernière position de chaque caractère dans le motif), décale le motif de plusieurs positions en cas de non-correspondance.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Parcours séquentiel d'un tableau — Parcourir un tableau élément par élément pour rechercher une occurrence, un extremum (maximum, minimum) ou calculer une moyenne ; le coût est linéaire : le nombre d'opérations est proportionnel à la longueur du tableau, et une recherche d'occurrence examine tout le tableau dans le pire cas.
- Dictionnaires par clés et valeurs — Un dictionnaire associe des valeurs à des clés uniques : lecture d'une valeur par sa clé, ajout ou modification d'une entrée, test d'appartenance d'une clé ; itération sur les clés, les valeurs ou les couples avec keys(), values() et items().
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (1). Difficulté 4 sur 5. Environ 5 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 4 sur 5 · ≈ 5 minutes
Énoncé
Lors d’une recherche de Boyer-Moore, un désaccord apparaît à l’indice j=29 du motif. Le caractère du texte en désaccord a sa dernière occurrence dans le motif à l’indice 21. Les indices commencent à zéro. Avec la seule règle du mauvais caractère, le décalage vaut max(1,j−dernièreOccurrence). Calculez-le. La longueur du texte restant est 68.
Donnez la valeur numérique demandée, avec au moins six chiffres significatifs si nécessaire.
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.