\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

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{PLFC (ENS Paris - Lyon 2002)}
   \unequestion   
    Trouver un algorithme en {\nf O}$(pq)$ donnant le plus long facteur
    commun à deux mots $u=u_0\ldots u_{p-1}$ et $v=v_0\ldots v_{q-1}$.
\paragraph*{Corrigé%
 \footnote{%
    D'après Bruno Petazzoni.
    }}\setcounter{questions}{0}\mbox{}
   \texte
    Pour tout $(i,j)\in[|0,p|]\times[|0,q|]$, soit $\ell_{i,j}$ la longueur
    du plus long préfixe commun aux deux mots
    $u_i\ldots u_{p-1}$ et $v_j\ldots v_{q-1}$. On a
    $$
     \ell_{i,j}=
     \begin{cases}
      0&\text{si $i=p$ ou $j=q$ ou $u_i\neq v_j$}\\
      1+\ell_{i+1,j+1}&\text{sinon,}
     \end{cases}
    $$
    ce qui permet de calculer et de stocker dans un tableau 
    tous les $\ell_{i,j}$
    (programmation dynamique).
    Ensuite, un parcours de ce tableau donne
    $\max_{i,j}\ell_{i,j}$ qui est
    la longueur d'un plus long facteur commun à $u$ et $v$.
    Chacune des deux étapes est en O$(pq)$.
\end{parenthese}\end{document}
