Algorithmique et séquences - recherche de motifs

Algorithme de Morris et Pratt

Question 1

Implémentez et testez l'algorithme naïf qui recherche les indices des occurences d'un motif dans un texte.

Question 2

Implémentez et testez l'algorithme de complexité linéaire qui construit la table des longueurs des plus longues frontières propres des préfixes d'une chaîne (algorithme étudié en cours).

Question 3

Implémentez et testez l'algorithme de Morris et Pratt pour la recherche de motifs (algorithme étudié en cours).

Algorithme de Rabin et Karp

Question 1

Implémentez et testez une fonction de hachage hash(char *s) de type rolling hash.

Question 2

Implémentez et testez une procédure hincr(int h, char c) telle que, si S est une chaîne et c,d sont deux caractères, alors la valeur retournée par hincr(hash(cS),d) est identique à celle retournée par hash(Sd). Cette procédure doit s'exécuter en temps constant.

Question 3

Implémentez et testez l'algorithme de Rabin et Karp pour la recherche de motifs.

Références bibliographiques :

• "Text Algorithms", M. Crochemore, W. Rytter, Oxford University Press, 1994

• "Algorithms on Strings, Trees and Sequences", D. Gusfield, Cambridge University Press, 1997

Données, utilitaires :

• Une séquence d'ADN

• Un texte littéraire (Les fourberies de Scapin, Molière)

• Quelques fonctions utilitaires en C pour les séquences

• Le fichier .h associé

• Vous pouvez essayer l'algorithme KMR (recherche du plus long motif répété K fois) sur les données séquence d'ADN et texte littéraire. Pour compiler KMR :
  cc kmr.c -o kmr