\documentclass[a4paper]{article}
\usepackage{entete}
\usepackage{algorithm,algofr}
\usepackage[table]{xcolor}
\author{Référence~: T.H. \textsc{Cormen}, C.E. \textsc{Leiserson}, R.L. \textsc{Rivest}, C. \textsc{Stein} \\ {\em Introduction to algorithms}
}
\title{Plus longue sous-séquence commune}
\date{2011-2012}

\begin{document}
\maketitle

Étant donnés deux mots $X=x_1\cdots x_m$ et $Y=y_1\cdots y_n$ sur un alphabet $\Sigma$, on cherche à savoir quel est le plus long sous-mot commun à $X$ et $Y$.

La solution naïve est d'énumérer tous les sous-mots de $X$, et de regarder ensuite s'ils sont aussi sous-mots de $Y$, mais cette solution est inefficace~: il y a $2^m$ sous-mots de $X$.

\begin{nota}
    Si $U$ est un mot de longueur $p$, on note $U_{p-j}$ le préfixe de $U$ de longueur $p-j$.
\end{nota}

Un algorithme plus efficace pourra être déduit du théorème de structure suivant~:

\begin{thm}[de structure des plus longues sous-séquences communes]
    Supposons que $Z=z_1\cdots z_k$ est une plus longue sous-séquence commune à $X$ et $Y$. Alors~:
    \begin{enumerate}[(i)]
        \item Si $x_m = y_n$, alors $z_k = x_m (=y_n)$ et $Z_{k-1}$ est une plus longue sous-séquence commune à $X_{m-1}$ et $Y_{n-1}$.
        \item Si $x_m \not= y_n$ alors $$\left( z_k \not= x_m \right) \Rightarrow Z\text{ est une plus longue sous-séquence commune à } X_{m-1} \text{ et } Y.$$
        \item Si $x_m \not= y_n$ alors $$\left( z_k \not= y_n \right) \Rightarrow Z\text{ est une plus longue sous-séquence commune à } X \text{ et } Y_{n-1}.$$

    \end{enumerate}
\end{thm}

\begin{proof}
    C'est plutôt facile~:
    \begin{enumerate}[(i)]
        \item $x_m=y_n$. Si $z_k \not= x_m$, alors $Zx_m$ est un sous-mot commun à $X$ et $Y$, ce qui contredit l'hypothèse de maximalité. D'où $z_k=x_m=y_n$.

        De plus, $Z_{k-1}$ est un sous-mot commun à $X_{n-1}$ et $Y_{m-1}$. Supposons qu'il existe un sous-mot commun $W$ de longueur plus grande que $k-1$.

        Alors, $Wx_m$ est de longueur plus grande que $k$, et $Wx_m$ est un sous-mot commun à $X$ et $Y$, d'où une contradiction.

        Donc $Z_{k-1}$ est une plus longue sous-séquence commune à $X_{m-1}$ et $Y_{n-1}.$
        \item $x_m\not= y_n$. Supposons $z_k\not= x_m$. Alors $Z$ est un sous-mot de $X_{m-1}$, et donc \em{a fortiori} un sous-mot commun à $X_{m-1}$ et $Y$.

        Supposons qu'il existe un sous-mot $W$ commun à $X_{m-1}$ et $Y$, de longueur plus grande. Alors $W$ est \em{a fortiori} un sous-mot commun à $X$ et $Y$, ce qui contredit l'hypothèse de maximalité de $Z$.

        \item {\em cf} (ii)
    \end{enumerate}
\end{proof}

Connaissant la plus longue sous-séquence commune au mot vide et n'importe quel mot, on peut en déduire une formule de récurrence sur la longueur de la plus longue sous-séquence commune de $X$ et $Y$. Si on note $c[i,j]$ la longueur de la plus longue sous-séquence commune à $X_{i}$ et $Y_j$, on a~:

\begin{equation}
    c[i,j] = \left\{
    \begin{array}{ll}
        0 & \text{si } i=0 \text{ ou } j=0 \\
        c[i-1,j-1]+1 & \text{si } i,j>0 \text{ et } x_i=y_j \\
        \max (c[i,j-1],c[i-1,j]) & \text{si } i,j>0 \text{ et } x_i \not= y_j
    \end{array}
    \right.
\end{equation}

Cette formule pourrait nous donner un algorithme récursif pour calculer $c[m,n]$, mais sa complexité serait à nouveau exponentielle. On va plut\^ot utiliser un algorithme de {\em programmation dynamique}.

Cet algorithme va calculer les uns après les autres les valeurs des $c[i,j]$, en utilisant la formule de récurrence, en remplissant le tableau par lignes.

\begin{algorithm}[!h]
\caption{Longueur-PLSC}
\label{plsc}
\begin{algorithmic}
    \REQUIRE $X,Y$ mots sur $\Sigma$
    \STATE $m \leftarrow \lon(X)$
    \STATE $n \leftarrow \lon(Y)$
    \FOR {$i=1$ to $m$}
        \STATE $c[i,0] \leftarrow 0$
    \ENDFOR
    \FOR {$j=0$ to $n$}
        \STATE $c[0,j] \leftarrow 0$
    \ENDFOR
    \FOR {$i=1$ to $m$}
        \FOR {$j=1$ to $n$}
            \IF {$x_i=y_j$}
                \STATE $c[i,j] \leftarrow c[i-1,j-1]+1$
                \STATE $b[i,j] \leftarrow "\nwarrow"$
            \ELSIF {$c[i-1,j] \geqslant c[i,j-1]$}
                    \STATE $c[i,j] \leftarrow c[i-1,j]$
                    \STATE $b[i,j] \leftarrow "\uparrow"$
                \ELSE 
                    \STATE $c[i,j] \leftarrow c[i,j-1]$
                    \STATE $b[i,j] \leftarrow "\leftarrow"$
            %    \ENDIF
            \ENDIF
        \ENDFOR
    \ENDFOR
    \STATE \RETURN $c$ et $b$
\end{algorithmic}    
\end{algorithm}

La matrice $b$ sert à noter "d'où on vient" pour calculer la valeur $c[i,j]$ d'une case. Grâce à ce tableau, on peut donc retrouver la plus longue sous-séquence commune à $X$ et $Y$ par l'algorithme~:

\begin{algorithm}[H]
\caption{PLSC}
\begin{algorithmic}
    \REQUIRE $X$ mot sur $\Sigma$, $b$ matrice calculée par Longueur-PLSC, $i,j$ indices.
    \IF {$i=0$ ou $j=0$}
        \STATE \PRINT ()
    \ENDIF
    \IF {$b[i,j] = "\nwarrow"$} 
        \STATE PLSC($b,X,i-1,j-1$)
        \STATE \PRINT $x_i$
    \ELSIF {$b[i,j] = "\uparrow"$}
        \STATE PLSC($b,X,i-1,j$)
    \ELSE 
        \STATE PLSC($b,X,i,j-1$)
    \ENDIF

\end{algorithmic}
\end{algorithm}


\begin{thm}
    La procédure Longueur-PLSC a une complexité en $\mathcal O(mn)$, et la procédure PLSC a une complexité en $\mathcal O (m+n)$.
\end{thm}

\begin{proof}
    Dans Longueur-PLSC, on a deux boucles "pour" imbriquées, et dans ces boucles des opérations en $\mathcal O(1)$. D'où la complexité.

    Dans PLSC, on réalise un "chemin direct" dans notre matrice $(i+1)\times (j+1)$, et donc ce chemin ne peut avoir plus de $i+j$ étapes.
\end{proof}

\begin{exm}
    On cherche la plus longue sous-séquence commune aux chaînes \texttt{BDCABA} et \texttt{ABCBDAB}. Le tableau construit par Longueur-PLSC est~:
    $$\begin{array}{|c|c|c|c|c|c|c|c|c|}
        \hline
          & j & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
        \hline
        i &  & y_j & \cellcolor{gray}B & D & \cellcolor{gray}C & A & \cellcolor{gray}B & \cellcolor{gray}A \\
        \hline
        0 & x_i& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        \hline
        1 & A  & \cellcolor{gray}0 & 0 \uparrow & 0 \uparrow & 0 \uparrow & 1 \nwarrow & 1 \leftarrow & 1 \nwarrow \\
        \hline
        2 & \cellcolor{gray}B  & 0 & \cellcolor{gray}1 \nwarrow & \cellcolor{gray}1 \leftarrow & 1 \leftarrow  & 1 \uparrow & 2 \nwarrow & 2  \leftarrow\\
        \hline
        3 & \cellcolor{gray}C  & 0 & 1 \uparrow & 1 \uparrow & \cellcolor{gray}2 \nwarrow & \cellcolor{gray}2 \leftarrow & 2 \uparrow & 2 \uparrow \\
        \hline
        4 & \cellcolor{gray}B  & 0 & 1 \nwarrow & 1 \uparrow & 2 \uparrow & 2 \uparrow & \cellcolor{gray}3 \nwarrow & 3 \leftarrow \\
        \hline
        5 & D  & 0 & 1 \uparrow & 2 \nwarrow & 2 \uparrow & 2 \uparrow & \cellcolor{gray}3 \uparrow & 3 \uparrow \\
        \hline
        6 & \cellcolor{gray}A  & 0 & 1 \uparrow & 2 \uparrow & 2 \uparrow & 3 \nwarrow & 3 \uparrow & \cellcolor{gray}4 \nwarrow \\
        \hline
        7 & B  & 0 & 1 \nwarrow & 2 \uparrow & 2 \uparrow & 3 \uparrow & 4 \nwarrow & \cellcolor{gray}4 \uparrow \\
        \hline
    \end{array}$$

    On suit les flèches (chemin grisé) et on note les lettres correspondant aux flèches obliques : \texttt{BCBA}.

\end{exm}


\end{document}
