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

  1. L'algorithme de Knuth-Morris-Pratt

    1. 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. Réponse


      p=0
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      b=0
      1
      1
      2
      3
      1
      2
      3
      2
      3
      4
      5
      6
      7
      2
      3
      4
      5
      6
      7
      8
      9
      10 (2)
      3
      4
      5
      6
      7
      8
      9
      1

    2. 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

      1. S[1]
        Réponse
        S[1]:=0;
      2. S[i] (i>1) quand tous les précédents S[j] sont déjà calculés.
        S[j]:=S[j-1]; /*il y a un facteur de longueur S[j] préfixe et suffixe
        de C[1..j-1] et candidat d'être rallongé par C[j] */
        tantque S[j]>0 et C[S[j]+1]!=C[j] faire
        S[j]:=S[S[j]] /* un candidat a échoué; essayer le prochain */
        fintantque;
        si C[S[j]+1]=C[j]
        alors S[j]:=S[j]+1
        finsi; /*sinon S[j] reste 0*/

  2. L'algorithme de Boyer et Moore

    1. 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).
      Réponse 4, 6, 9, 11, 15, 17, 21, 23, 25, 29
    2. 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 ?
      Réponse
      plusieurs: prendre le plus à droite
      aucune: si f est le plus long facteur de C qui est en même temps préfixe de C et suffixe de bc, avancer de façon à aligner son occurrence comme préfixe de abcdbc avec le suffixe de l'occurrence de bc qu'on vient de trouver.
      (Y compris dans le cas où f est le mot vide.)



File translated from TEX by TTH, version 3.05.
On 16 Dec 2005, 17:44.

symboles bricolés pour netscape par sed