💻 NSITleTerminaleSans inscription

Recherche textuelle — Boyer-Moore

Programme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte

NSI terminale : recherche d'un motif dans un texte, algorithme naïf, algorithme de Boyer-Moore-Horspool, table de sauts, efficacité.

La règle d'or

Boyer-Moore compare le motif de droite à gauche et saute grâce à une table précalculée, ce qui évite de tester chaque position du texte.

L'erreur que tout le monde fait

Comparer de gauche à droite dans Boyer-Moore.

L'algorithme compare depuis la fin du motif : c'est ce qui permet les grands sauts.

Toujours partir du dernier caractère du motif.

Télécharger la fiche A4 — Recherche textuelle — Boyer-MooreVersion à trous, pour se testerSans compte, sans adresse e-mail · exercices et corrigé plus bas.

Notions à maîtriser

  • Boyer-Moore
  • recherche textuelle
  • algorithme
  • NSI terminale
  • NSI
  • Python
1

Réviser

Chercher un mot dans un livre, un gène dans une séquence d'ADN, un virus dans un fichier : il faut trouver un motif dans un texte, le plus vite possible. L'algorithme de Boyer-Moore évite de tester chaque position une à une.

1L'algorithme naïf

Règle

On place le motif à chaque position du texte et on compare caractère par caractère. Pour un texte de longueur n et un motif de longueur m, le nombre de comparaisons peut atteindre environ n × m.

2L'idée de Boyer-Moore

Définition

Boyer-Moore-Horspool — Version simplifiée de Boyer-Moore : on compare le motif au texte de droite à gauche ; en cas d'échec, on décale le motif grâce à une table de sauts calculée à l'avance.

Définition

table de sauts — Pour chaque caractère du motif (sauf le dernier), distance entre sa dernière occurrence et la fin du motif ; un caractère absent du motif permet de sauter de toute la longueur m.

3Efficacité

Règle

Plus le motif est long et l'alphabet varié, plus les sauts sont grands : on lit bien moins de caractères que l'algorithme naïf. C'est le principe utilisé par la fonction « Rechercher » des éditeurs de texte.

Exemple

Calcule la table de sauts du motif « NSI ».

  1. Longueur m = 3.
  2. N est à 2 positions de la fin : saut 2 ; S à 1 position : saut 1.
  3. Tout autre caractère : saut 3.

La table de sauts indique de combien décaler le motif selon le caractère du texte aligné avec la fin du motif.

Piège

Comparer de gauche à droite dans Boyer-Moore.

Pourquoi — L'algorithme compare depuis la fin du motif : c'est ce qui permet les grands sauts.

Le réflexe — Toujours partir du dernier caractère du motif.

Appliquer Boyer-Moore-Horspool

  1. Calculer la table de sauts du motif.
  2. Aligner le motif au début du texte.
  3. Comparer de droite à gauche.
  4. Décaler selon la table en cas d'échec, jusqu'à la fin du texte.
  • ▢Ai-je défini le vocabulaire ?
  • ▢Mon code est-il testé sur un exemple ?
  • ▢Ai-je traité les cas limites ?
  • ▢Ai-je justifié la complexité ou le résultat ?

L'essentiel en 3 points

  • ·Algorithme naïf : jusqu'à n × m comparaisons.
  • ·Boyer-Moore-Horspool : comparaison de droite à gauche, table de sauts.
  • ·Grands sauts quand le motif est long : bien plus rapide.
2

Imprimer

Fiche PDF — Recherche textuelle — Boyer-Moore

Gratuit · sans compte

Trois documents à imprimer, 4 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.

Au sommaire du cours

  1. 1. L'algorithme naïf
  2. 2. L'idée de Boyer-Moore
  3. 3. Efficacité

Conforme au programme officiel · version 2026.2.

3

Exercices corrigés

1

Naïf

Calculer
  1. a.Texte de 1 000 caractères, motif de 10 : ordre de grandeur des comparaisons en naïf au pire ?
›Voir le corrigé
  1. Environ 10 000.
2

Table

Calculer
  1. a.Table de sauts de « CODE ».
›Voir le corrigé
  1. C : 3, O : 2, D : 1, autres : 4.
3

Sens

Connaître
  1. a.Dans quel sens compare-t-on dans Boyer-Moore ?
›Voir le corrigé
  1. De droite à gauche (fin du motif vers le début).
4

Saut

Analyser
  1. a.Le caractère du texte face à la fin du motif n'est pas dans le motif. De combien décale-t-on ?
›Voir le corrigé
  1. De la longueur du motif.
5

Naïf

Programmer
  1. a.Écris recherche_naive(texte, motif) renvoyant la première position ou -1.
›Voir le corrigé
  1. Pour i de 0 à len(texte) - len(motif) : si texte[i:i+len(motif)] == motif, renvoyer i ; à la fin, renvoyer -1.
6

Usage

Analyser
  1. a.Cite un domaine où la recherche textuelle rapide est cruciale.
›Voir le corrigé
  1. La bio-informatique (séquences d'ADN), les antivirus, les moteurs de recherche.

Ce qui rapporte des points, ce qui en coûte

  • Vocabulaire2 ptsPerdu si : Définitions floues
  • Code juste et testé2 ptsPerdu si : Cas limites oubliés
  • Justification1 ptPerdu si : Résultat non expliqué
4

La méthode

Appliquer Boyer-Moore-Horspool

  1. 1

    Calculer la table de sauts du motif.

  2. 2

    Aligner le motif au début du texte.

  3. 3

    Comparer de droite à gauche.

5

Se tester

NSITerminale
Question 1
Que contient la table de décalage de Boyer-Moore-Horspool ?

Aucun compte requis — réponds, la correction s'affiche aussitôt.

Signaler une erreur

Garder ta progression ?

Tes réponses sont déjà comptées dans ce navigateur. Un compte gratuit les conserve d'un appareil à l'autre et débloque le suivi de tes points faibles.

Avec un compte gratuit

La fiche et les exercices restent ouverts. Le compte, lui, te dit quoi travailler.

1 · Ta séance du jour

Recherche textuelle — Boyer-Moore

3 minutes, sur ce qui résiste

Commencer

2 · Ta progression, vue aussi par tes parents

  • Maths72 %
  • Français58 %
  • Histoire-géo41 %
  • SVT64 %

3 · Tes erreurs, rejouées

  • Ta réponse, et où elle déraille
  • La bonne, avec l'explication
Rejouer

Gratuit, sans carte bancaire. Les chiffres ci-dessus sont un exemple d'affichage.

Questions fréquentes

Recherche textuelle — Boyer-Moore : c'est en quelle classe ?

Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.

Que faut-il savoir sur Recherche textuelle — Boyer-Moore ?

NSI terminale : recherche d'un motif dans un texte, algorithme naïf, algorithme de Boyer-Moore-Horspool, table de sauts, efficacité. Les notions à maîtriser sont : Boyer-Moore, recherche textuelle, algorithme, NSI terminale, NSI, Python.

Où télécharger la fiche PDF de Recherche textuelle — Boyer-Moore ?

Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 4 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.

Le corrigé de Recherche textuelle — Boyer-Moore est-il fourni ?

Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.

Recherche textuelle — Boyer-Moore peut-il tomber au Baccalauréat ?

Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.

Comment réviser Recherche textuelle — Boyer-Moore efficacement ?

Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.

Faut-il un compte pour s'entraîner sur Recherche textuelle — Boyer-Moore ?

Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.

Notions voisines

Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.

Un ordinateur pour le lycée

Python dès la seconde, exposés, espace numérique de travail : un portable qui suit jusqu'au bac.

  • Petit budget, 16 Go

    Acer Aspire Go 15 (Ryzen 5 7430U, 16 Go, 512 Go)

  • Le prix de référence

    HP 15 (Core i5-1334U, 16 Go, 512 Go)

  • Léger, pour le cartable

    Acer Swift Go 14 AI

En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.

Pour réviser le bac

Les annales de la matière, et le grand oral.

  • Grand oral

    Prépabac Le Grand Oral, terminale générale, bac 2027

    Hatier

  • Réviser la philosophie

    Prépabac philosophie, terminale générale, bac 2027

    Hatier

En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.