\input exos.mac
\doublecrochets
\guillemets
%----------------------------------------------------------------------
\ex ENS Cachan MP 2002
On d\'efinit pour deux mots $u$ et $v$ la relation $R$ par~: $u\,R\,v$ si et
seulement s'il existe des mots $x,y,z$ tels que $u = xyz$ et $v=x\tilde yz$
o\`u $\tilde y$ d\'esigne le miroir de $y$.

\qq Donner un algorithme qui d\'ecide si $u\,R\,v$.
\reponse{Essayer toutes les possibilit\'es pour $y$. Algorithme en $|u|^3$.}
\qq Montrer que pour toute lettre $a$ on a $(u\,R\,v) \<=> (au\,R\,av)$. En d\'eduire
    un meilleur algorithme pour d\'ecider si $u\,R\,v$.
\reponse{On montre $(u\,R\,v)\<=>(au\,R\,av)\<=>(ua\,R\,va)$ par disjonction de cas.
    Algorithme~: retirer les lettres identiques au d\'ebut de $u$ et $v$ et \`a la fin
    de $u$ et $v$. Tester si $\widetilde{u'} = v'$ o\`u $u'$ et $v'$ sont les
    mots restants. Complexit\'e~: $O(|u|)$.}
\qq Soit un mot $u$. On l'\'ecrit en boucle. Tout mot obtenu en cassant cette boucle
    est dit \'egal \`a~$u$ modulo une rotation. Trouver un algorithme quadratique
    utilisant le pr\'ec\'edent, qui d\'ecide \'etant donn\'es deux mots $u$ et $v$, s'il existe des
    mots $u'$ et $v'$ \'egaux respectivement \`a $u$ et $v$ modulo une rotation,
    et tels que $u'\,R\,v'$.
\reponse{Soit $R'$ la nouvelle relation. On a $(u\,R'\,v) \<=>$
    il existe $v'$ d\'eduit de $v$ par rotation tel que $(u\,R\,v')$ ou $(\tilde u\,R\,v')$.}


\answerwrite{\xe\SV}\xe\SV
\bye
