Un peu d'algorithmique
Recherche textuelle
La plupart des applications comme celle sur laquelle vous lisez ces lignes, possèdent une fonction de recherche textuelle.
En général pour y accéder on utilise la combinaison de touches CTRL + F
Trouver les occurrences d'une chaîne de caractères (motif ou mot) dans un texte est un problème qui se rencontre fréquemment dans les éditeurs de texte.
Les algorithmes de recherche de chaîne de caractères sont également utilisé pour trouver une séquence ADN par exemple ou pour rechercher des pages web correspondantes à une recherche Internet.
Dans le domaine de la génétique, on peut par exemple rechercher :
des 'mots' courts comme la séquence ATG(qui code une méthionine (Met)) correspondant au codon initiateur sur le brin sens (codant, non transcrit), marquant le début de la séquence transcrite d'un gène,
des 'mots' plus longs afin de déterminer la présence d'allèles particuliers de gène.
Ou plus simplement combien de fois apparaît le mot "Valjean" dans le premier tome des misérables de Victor Hugo.
Le TD
Ce notebook après une approche naïve, vous présente l'algorithme de Boyer-Moore-Horspool publié en 1980 par Nigel Horspool, un professeur à l'université de Victoria au canada.
