Thierry Lecroq (LIFAR, Universite de Rouen)

Nous présentons l’algorithme de Boyer-Moore et deux de ses améliorations. L’algorithme de Boyer-Moore effectue les comparaisons entre les lettres du mot et celles du texte de la droite vers la gauche ce qui lui permet d’avoir un très bon comportement en pratique. Cole à montré en outre qu’il effectuait au plus $3n$ comparaisons entre lettes du mot et du texte pour la recherche de la première occurrence d’un mot non-périodique. La première amélioration que nous présentons est l’algorithme Turbo-BM qui effectue au plus $2n$ comparaisons pour rechercher toutes les occurrences de $x$. Enfin, nous présentons l’algorithme d’Apostolico-Giancarlo qui effectue $3n/2$ comparaisons dans le pire des cas.