Analyse en moyenne de la recherche de motifs

Nous proposons un sch\'ema g\'en\'eral d'analyse en moyenne pour les algorithmes de recherche de motifs avec preprocessing du motif. Il repose principalement sur les langages et la combinatoire sur les mots\,; certains outils probabilistes sont aussi utilis\'es. Les distributions des caract\`eres dans le texte et le motif sont suppos\'ees markoviennes ou stationnaires. Nous consid\'ererons l'algorithme (lin\'eaire) de Morris-Pratt et ses variantes. Nous exprimerons les constantes de lin\'earit\'e par des formules alg\'ebriques closes. Quand les distributions sont uniformes, ces constantes ne d\'ependent que de la cardinalit\'e $q$ de l'alphabet.