Utilisateur:Regards sur sciences/agreg/leçons/9. Algorithmique du texte. Exemples et applications.
Recherche de motifs dans une séquence modifier
Étant donné un motif, suite de m caractères, l'objectif est de déterminer les occurrence de ce motif dans un texte de longueur n. Après avoir introduit les applications de ce problème (traitement de texte, bioinformatique,...), ce problème sera utilisé pour illustrer la notion de raffinement d'algorithme en partant de l'algorithme naïf, puis en utilisant la notion de préfixe d'un motif pour construire un automate et terminer avec un algorithme basé sur les suffixes. Ce cours permettra d'aborder, de manière élémentaire, le concept d'expression régulière et de reconnaissance de mots d'un langage.
Référence :
Consulter le chapitre 32 [CRLS] traite du problème, il explique l'approche à l'aide de l'automate des préfixes. L'algorithme de Horspool (version simplifiée de l'algorithme de Boyer Moore) est détaillée dans le [BBC]