Révision

Ce qu’il faut savoir

• les algorithmes permettant de rechercher un motif (suite de lettres) dans un texte ont une grande importance en informatique

• L'algorithme de Boyer-Moore effectue un prétraitement du motif. Cela signifie que l'algorithme "connait" les caractères qui se trouvent dans le motif

• Dans l'algorithme de Boyer-Moore on commence la comparaison motif-chaine par la droite du motif. Par exemple pour le motif CGGCAG, on compare d'abord le G, puis le A, puis C...on parcourt le motif de la droite vers la gauche

• Dans le cas de l'algorithme "naïf", les décalages du motif vers la droite se faisaient toujours d'un "cran" à la fois. L'intérêt de l'algorithme de Boyer-Moore, c'est qu'il permet, dans certaines situations, d'effectuer un décalage de plusieurs crans en une seule fois.

• plus le motif est grand et plus l'algorithme de Boyer-Moore sera efficace par rapport à l'algorithme "naïf"

Ce qu’il faut savoir faire

Vous devez être capable d'appliquer l'algorithme de Boyer-Moore sur un cas simple.