L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Bob Boyer et J Strother Moore en 1977.
L'algorithme de Boyer-Moore pré-traite la sous-chaîne (c'est-à-dire la chaîne recherchée), et non pas le texte (c'est-à-dire la chaîne dans laquelle la recherche est effectuée), à l'inverse de certains algorithmes, qui amortissent le coût du prétraitement du texte en effectuant de très nombreuses recherches répétitives. Le coût d'exécution de l'algorithme de Boyer-Moore peut être sub-linéaire, c'est-à-dire qu'il n'a pas besoin de vérifier chacun des caractères du texte, mais peut au contraire sauter certains d'entre eux. En général, l'algorithme devient plus rapide lorsque la longueur de la sous-chaîne s'allonge. Cette efficacité provient du fait que, pour chaque tentative infructueuse de correspondance entre les deux chaînes (texte et sous-chaîne), il utilise les informations déduites de cet échec pour éliminer le plus grand nombre possible de positions à vérifier.
En comparaison des méthodes de recherches basiques par la méthode de « force brute » (qui recherche la sous-chaîne en commençant par chercher partout dans le texte une correspondance du premier caractère de la sous-chaîne, puis en vérifiant si les caractères suivants correspondent) et dont la complexité en temps (calculée par exemple selon le nombre de paires de caractères à comparer) croit en O(L · K) où K est la longueur de la sous-chaîne clé recherchée, et L la longueur où l’on recherche s’il existe au moins une occurrences de la clé, l’algorithme de Boyer-Moore peut trouver les occurrences en un temps :
Le cas moyen pour établir s’il y a correspondance ou non requiert environ (3 · K) comparaisons. La preuve est due à Richard Cole.
Dans le pire cas, les performances de l'algorithme de base (sans la variante avec la seconde table de vérification des occurrences) pour trouver toutes les correspondances est de l'ordre de O(K · L). Le pire cas se produit quand la sous-chaîne consiste en une répétition d’un unique caractère, et que le texte correspond à la répétition de (K - 1) fois ce même caractère, précédé par un seul autre caractère différent. Dans ce cas de figure, l’algorithme doit vérifier (L - K+ 1) décalages différents dans le texte pour chaque correspondance. Or, chacune de ces vérifications nécessite K comparaisons.
En raison de l’intérêt de la variante avec la seconde table qui permet un comportement sous-linéaire même dans le pire cas, cette variante est décrite ici (et est celle aujourd'hui intégrée dans de nombreuses librairies de traitement du texte pour C/C++, Java, etc.).