Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Mars 1999

Les algorithmes de recherche de mot du type Boyer-Moore

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr