\documentclass[12pt,a4paper,twoside]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen

\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE
%\newcommand{\MlPic}[1]{\mbox{}\\FIGURE\\}    %COMMENTER CETTE LIGNE

\renewcommand{\d}{\,.\,.\,}

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{Algorithme de Boyer-Moore (ENS 2002)%
    \footnote{%
      D'après
      M. Crochemore, C. Hancart, T. Lecroq.
      \emph{Algorithmique du texte}.
      Vuibert, 2001.%
    }}
   \texte
    On s'intéresse au problème de la recherche de la première
    occurrence d'un motif $x=x[0\d m-1]$ dans un mot
    $y=y[0\d n-1]$. Pour cela, on peut appliquer
    l'algorithme naïf suivant qui déplace le motif de gauche à droite
    le long du mot et qui, pour chaque position du motif, teste
    s'il coïncide avec le facteur correspondant de $y$  en comparant
    les lettres du motif et du facteur de droite à gauche.
    \numeroter
    \begin{algorithm}
     {\soit} \emph{Recherche\_naïve}$(x,y)=$\ii\ls
       {\soit} $j$ {\affecte} $m-1$ {\dans}\ls
       {\tantque} $j<n$ {\faire}\ii\ls
         $i$ {\affecte} $m-1$\ls
         {\tantque} $i\geq0$ {\et} $x[i]=y[j-m+1+i]$ {\faire}
           $i$ {\affecte} $i-1$\ls
         {\si} $i<0$ {\alors} {\renvoyer} $j-m+1$ (* $x=y[j-m+1\d j]$ *)\ls
         $j$ {\affecte} $j+1$\di\ls
       \textbf{échouer} (* le motif n'apparaît pas *)         
    \end{algorithm}
   \question\nf Heuristique du mauvais caractère\sl\par
    Donner une méthode de calcul, à partir du motif $x$,
    d'un tableau $mc$ qui associe un entier à toute lettre $\ell$
    de manière que l'on puisse remplacer la ligne {\nf7} de l'algorithme
    naïf par l'instruction suivante:
    \nonnumeroter
    \begin{algorithm}
     $j$ {\affecte} $j+\max(1,i-mc[y[j-m+1+i]])$
    \end{algorithm}
   \question\nf Heuristique du bon suffixe\sl\par
    Donner la définition d'un tableau $bs[0\d m-1]$, calculable
    à partir de $x$, tel que l'on puisse remplacer
    avantageusement la ligne {\nf7} de l'algorithme naïf par
    \nonnumeroter
    \begin{algorithm}
     $j$ {\affecte} $j+\max(bs[i],i-mc[y[j-m+1+i]])$
    \end{algorithm}
   \question
    Donner un algorithme en {\nf O}$(m)$ qui renvoie la 
    \emph{table du bon suffixe} $bs$. On pourra commencer par calculer
    la \emph{table des suffixes} $s[0\d m-1]$ définie par
    $s[i]=$ la longueur du plus long suffixe commun à $x$ et
    $x[0\d i]$.
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
   \cquestion
    Dans l'algorithme naïf, l'instruction $j\leftarrow j+1$ de la ligne 7
    effectue un décalage d'une unité du motif vers la droite quand la
    lettre $a=x[i]$ diffère de $b=y[j-m+1+i]$ (le \emph{mauvais caractère}).
    Or si l'occurrence la plus à droite de la lettre $b$ dans $x$
    se trouve à gauche de $a=x[i]$: $b=x[i']$ avec $i'<i$,
    on peut effectuer un décalage de $x$ de $i-i'$ caractères sans risquer
    de perdre une occurrence de $x$ dans $y$. Dans la figure suivante, la
    flèche symbolise ce décalage.
    \begin{center}\MlPic{cl008-01}\end{center}
    Si la lettre $b$ n'apparaît pas dans le motif, un décalage autorisé
    est $i+1$:
    \begin{center}\MlPic{cl008-02}\end{center}
    Finalement, on pourra remplacer la ligne 7 par celle indiquée à
    condition de définir  le tableau $mc$ par 
    $$
     mc[\ell]=
       \begin{cases}
        \max\{i\,|\,x[i]=\ell\}&\text{si $\ell$ apparaît dans $x$}\\
        -1&\text{sinon.}
       \end{cases}
    $$
    Le code suivant construit $mc$.
    \numeroter
    \begin{algorithm}
     \mbox{\hspace{1.3mm}}{\pour} chaque lettre $\ell$ {\faire} $mc[\ell]$ {\affecte} $-1$\ls
     {\pour} $i$ {\affecte} $0$ {\a} $m-1$ {\faire} $mc[x[i]]$ {\affecte} $i$
    \end{algorithm}
   \cquestion
    Reprenons la situation de la question précédente dans laquelle
    $u=x[i+1\d m-1]=y[j-m+2+i\d j]$ et $a=x[i]\neq b=y[j-m+1+i]$.
    Soit $d$ une valeur du décalage à droite du motif
    pour laquelle il y a coïncidence du motif et du facteur de $y$
    correspondant.
    Si $d\leq i$,
    alors $u=x[i+1\d m-1]=x[i+1-d\d m-1-d]$ et $a=x[i]\neq x[i-d]$:
    \begin{center}\MlPic{cl008-03}\end{center}
    Si $i<d<m$, alors le préfixe $v=x[0\d m-1-d]$ de $x$ est aussi
    suffixe de $x$:
    \begin{center}\MlPic{cl008-04}\end{center}    
    On définit donc $bs[i]$ comme le plus petit des 
    $i$-\emph{décalages} où on appelle $i$-décalage
    un entier $d$ tel que
    \begin{itemize}
     \item[] 
      ou bien $1\leq d\leq i$,
      $x[i+1\d m-1]=x[i+1-d\d m-1-d]$ et $x[i]\neq x[i-d]$;
     \item[]
      ou bien $i<d\leq m$
      et $x[d\d m-1]=x[0\d m-1-d]$.
    \end{itemize}
   \cquestion
    On donne  d'abord un algorithme de calcul de la table
    des suffixes $s$. \par
    $s[m-1]=m$ puis on calcule $s[i]$, pour
    $i=m-2,m-3,\dotsc,0$ en introduisant deux variables
    $f$ et $g$ auxquelles on impose, pour $i=m-2,m-3,\dotsc,0$
    mais pas pour $i=m-1$, l'invariant suivant:
    \begin{align*}
     &i\leq f\leq m-2\\
     &g=f-s[f]\\
     &g\text{ est minimum.}
    \end{align*}
    Noter que, au départ, $f$ n'est pas définie et on donne à $g$
    la valeur $m-1$ afin que la condition $i>g$ soit fausse
    dans le corps de la boucle.
    \begin{center}\MlPic{cl008-05}\end{center}
    \numeroter
    \begin{algorithm}
     {\soit} \emph{Table\_des\_suffixes}$(x)=$\ii\ls
       $g$ {\affecte} $m-1$\ls
       $s[m-1]$ {\affecte} $m$\ls
       {\pour} $i$ {\affecte} $m-2$ {\decra} $0$ {\faire}\ii\ls
         {\si} $i>g$ {\et} $s[i+m-1-f]<i-g$ {\alors}\ii\ls
           $s[i]$ {\affecte} $s[i+m-1-f]$\di\ls
         {\sinon}\ii\ls
           $g$  {\affecte} $\min(g,i)$\ls
           $f$  {\affecte} $i$\ls
           {\tantque} $g\geq0$ {\et} $x[g]=x[g+m-1-f]$ {\faire}
             $g$  {\affecte} $g-1$\ls
           $s[i]$  {\affecte} $f-g$\di\di\ls
       {\renvoyer} $s$
    \end{algorithm}
    La complexité est bien O$(m)$ car
    $g$ est décrémenté dans le corps de la boucle de la ligne 10.
    \evp
    On propose l'algorithme suivant pour calculer la
    table du bon suffixe:
    \begin{algorithm}
     {\soit} \emph{Table\_du\_bon\_suffixe}$(x,s)=$\ii\ls
       $i$ {\affecte} $0$\ls
       {\pour} $d=1$ {\a} $m$ {\faire}\ii\ls
         {\si} $d=m$ \textbf{ou} $s[m-1-d]=m-d$ {\alors}\ii\ls
           {\tantque} $i<d$ {\faire}\ii\ls
             $bs[i]$ {\affecte} $d$\ls
             $i$ {\affecte} $i+1$\di\di\di\ls
       {\pour} $d$ {\affecte} $m-1$ {\decra} $1$ {\faire}\ii\ls
         $bs[m-1-s[m-1-d]]$ {\affecte} $d$\di\ls
       {\renvoyer} $bs$
    \end{algorithm}
    Dans une première étape, lignes 2 à 7, on donne à $bs[i]$ la valeur
    du plus petit $i$-décalage $>$ à $i$. On remarque
    pour cela qu'un entier $d>i$ est un tel décalage ssi
    il vérifie la condition suivante:
    $$d=m\text{ ou }(d<m\text{ et }s[m-1-d]=m-d)$$
    \begin{center}\MlPic{cl008-06}\end{center}
    Soit donc $1\leq d_1<\dotsb<d_p=m$ l'ensemble des $d$
    vérifiant cette condition; alors, si $d_{k-1}\leq i<d_k$ (on convient
    $d_0=0$), le plus petit $i$-décalage $>$ à $i$ est $d_k$.
    \evp
    Il reste, dans une deuxième étape, lignes 8 et 9, à mettre à jour
    $bs[i]$ dans le cas où il existe un $i$-décalage $d\leq i$.
    Dans ce cas, $i=m-1-s[j]$ où $j=m-1-d$. A toute valeur de $d$
    correspond donc un unique $i$ et il suffit de parcourir 
    les valeurs possibles de $d$ en ordre décroissant pour être
    assuré que chaque $bs[i]$ se verra affecté du $d$ minimum.
    \begin{center}\MlPic{cl008-07}\end{center}        
    En fait $d=i+1$ pour les valeurs de $d$ telles que $s[j]=j+1$
    et, dans ce cas, l'affectation $bs[i]$ {\affecte} $d$ n'a pas d'effet
    car $bs[i]$ a déjà la valeur $i+1$ d'après la première étape.\par
    L'algorithme est en O$(m)$ car $i$ augmente dans le corps de la
    boucle des lignes 5 à 7.
    \evp
    On peut montrer que l'algorithme de Boyer-Moore est O$(n)$.
\end{parenthese}\end{document}
