Licence Info
Algorithmique Avancée
TD 12 : décembre 2005
Les algorithmes de recherche de facteurs dans un mot
On considère des recherches dans le mot (texte)
aabaababacdbabacdbaeabacdbaeaa
- L'algorithme de Knuth-Morris-Pratt
- Si on cherche
les occurrences de abacdbaeab, tracer l'évolution des
variables
p (position dans le texte de la lecture) et b
(le nombre de
``bonnes'' lettres déjà trouvées au début
d'une occurrence possible)
pendant toute l'exécution de l'algorithme.
- L'algorithme utilise un tableau (disons S)
où S[i] est la longueur du suffixe le plus long de
C[1..i] (sauf C[1..i] lui même)
qui est aussi un préfixe de la cible C ; donner en
Exalgo
le calcul de
- S[1]
- S[i] (i>1) quand tous les
précédents S[j] sont déjà
calculés.
- L algorithme de Boyer et Moore
- Dans une recherche d'occurrences de bacd, quelle
est l'évolution
de la variable indiquant les positions possibles de la fin d'une
occurrence
(vous pouvez supposer qu'après la découverte d'une
occurrence avec
sa fin à la position i, la recherche va
redémarrer avec i+4
comme prochain candidat d'être la fin).
- Si on cherche une cible comme abcdbc et, à
une position possible,
on trouve le facteur bc à la fin mais pas
précédé par d,
on peut avancer la position de recherche par 3 lettres de façon
à aligner le bc trouvé avec l'autre occurrence
de bc
dans la cible. Que devrait on faire s'il y a plusieurs autres
occurrences
du facteur trouvé dans la cible ? Et s'il n'y en a aucune ?
File translated from
TEX
by
TTH,
version 3.05.
On 12 Dec 2005, 12:01.
symboles bricolés pour netscape par sed