Terminale NSI — Sommaire du chapitre

Recherche textuelle

2 séances de 2h

Chapitre consacré à la recherche textuelle : comment retrouver un motif (une sous-chaîne) dans un texte, de l'approche la plus simple à une version nettement plus efficace. Deux séances de 2h, pensées pour pratiquer vite avec des exemples concrets.

Prérequis
Manipulation de chaînes de caractères, boucles, fonctions. Aucune notion de complexité formelle n'est nécessaire : ce chapitre reste sur une approche intuitive et expérimentale (comptage de comparaisons, mesures de temps).
Séance 1 / 2

Le problème et l'algorithme naïf

Vocabulaire (motif, texte, occurrence), recherche naïve, comptage de comparaisons, mesures de temps.
Séance 2 / 2

Boyer-Moore-Horspool

Comparaison de droite à gauche, table de décalage, implémentation, comparaison expérimentale avec l'algorithme naïf.