Quelle est une caractéristique de l'algorithme de Boyer-Moore, qui recherche un motif dans une chaîne de caractères ?

Réponse : A. Il compare le motif en partant de son dernier caractère et utilise des informations, par exemple le fait que le caractère du texte en désaccord n'apparaît pas dans le motif, pour décaler le motif d'un grand pas en une fois

L'algorithme de Boyer-Moore compare le motif à partir de son dernier caractère et précalcule des tables de sorte que, par exemple, si le caractère du texte en désaccord n'apparaît pas du tout dans le motif, tout le motif puisse être décalé au-delà de ce caractère. Sur un texte en langue naturelle, il peut ainsi sauter de nombreux caractères sans les comparer. Pour un texte de longueur n et un motif de longueur m, la méthode naïve qui décale d'un caractère à la fois et compare tout prend O(nm) dans le pire cas. L'algorithme KMP utilise lui aussi les informations de désaccord pour décaler le motif, mais il compare depuis le début du motif et garantit O(n + m) même dans le pire cas.