Algorithmique du texte

Recherche de motifs dans un texte

L'objectif de ce TP est :

• d'une part d'implémenter les algorithmes vus en TD,
• d'autre part d'afficher pas à pas l'état des variables pour comprendre leur fonctionnement,
• enfin de mesurer en pratique les performances des algorithmes vus en cours. Vous vous servirez du fichier bench.c, qui contient le code nécessaire pour mesurer le temps d'exécution d'un fragment de programme.

Travail à réaliser (2h) :

• Implémenter les deux versions de l'algorithmes naïf,
• Implémenter l'algorithme "pas aussi naïf" qui compare à partir de la deuxième position,
• Implémenter la version simplifiée de l'algorithme de Boyer-Moore,
• Implémenter une (des) procédure(s) d'affichage évoluée(s),
• Mesurer le temps d'exécution de ces algorithmes sur des exemples,
• Modifier les algorithmes pour qu'ils retournent toutes les occurences des motifs et non pas uniquement la première.
  Note : "Retourner" ne veux pas dire "afficher".