#code #algorithme

Boyer-Moore est un algorithme permettant de faire de la recherche de texte rapide, bien plus rapide que la recherche exhaustive, car permet de skipper un bon nombre de comparaisons.

Soit P le pattern recherché dans le texte T. T est parcouru de gauche à droite, cependant la comparaison commence par la fin de P (donc de droite à gauche)

L’algorithme est basé sur deux règles permettant de skipper des alignements, et choisira la max entre ces deux règles. Les règles entrent en compte dès qu’un character est mismatched 1. La “bad character rule” permet de skipper des alignements jusqu’à la prochaine occurence du character dans le pattern 2. La “good suffix rule” permet de skipper jusqu’à ce que le même suffit soit trouvé dans le pattern

Pour que ces règles soient rapide à executer, une lookup table est calculée avant la search et permet d’appliquer chaque règles en O(1).