Performances des algorithmes de recherche de motifs

Nous proposons une m\'ethode g\'en\'erale pour \'evaluer le comportement moyen des algorithmes de recherche de motifs. Elle repose principalement sur les langages et la combinatoire des mots. La puissance de l'approche permet de l'appliquer \`a une grande classe d'algorithmes, c'est-\`a-dire ceux qui sont bas\'es sur un pr\'etraitement du motif. Nous consid\'erons une distribution des caract\`eres tr\`es g\'en\'erale, c'est-\`a-dire une d\'ependance markovienne d'ordre 1 entre les caract\`eres. Cette mod\'elisation s'applique notamment aux langages naturels et aux s\'equences d'ADN. Nous consid\'ererons les exemples de Morris-Pratt et Boyer-Moore-Horspool. Nous montrerons que le temps de recherche moyen, exprim\'e en nombre de comparaisons texte-motif, est lin\'eaire, et calculerons la constante de lin\'earit\'e.