Numérique et sciences informatiques (spécialité) · Terminale · Algorithmique

Recherche textuelle et algorithme de Boyer-Moore

• La recherche textuelle consiste à trouver une ou toutes les occurrences d'un motif dans un texte .
• La méthode naïve teste chaque position du texte et compare le motif caractère par caractère : elle peut effectuer beaucoup de comparaisons.
• Boyer-Moore compare le motif de droite à gauche et lit dans une table de décalage de combien avancer, pour sauter des positions inutiles .
• La table de la version simplifiée (Horspool) se construit en une seule passe sur le motif, sans son dernier caractère.