Problème : quelle est la plus longue suite {w} commune (en abrégé plssc) à {u=(u_{0},...,u_{m-1}\quad )} et {v=(v_{0},...,v_{n-1}\quad )?}
{m} Il y a 2 suites extraites d’une suite de longueur {m_{n}(}autant que de parties de l’ensemble des indices). Un algorithme na ̈if consisterait à former les 2 sous-suites de {u} et les 2 sous-suites de {v.} On ne garderait que les couples {(u^{\prime },v^{\prime })} pour lesquels {m} {u^{\prime }=v^{\prime }} et on renverrait la plus grande de ces longueurs communes. Ce n’est pas raisonnable.
7.4.1 Étude du problème
On cherche à former une plssc {w=(w_{0},...,w_{p})} de {u=(u_{0},...,u_{m-1}\quad )} et {v=(v_{0},...,v_{n-1}\quad ).}
Les observations suivantes sont faciles :
- Si {u_{0}=v_{0}(}valeur commune notée {w_{0})} et si {(w_{1},...,w_{p})} est une plssc de {(u_{1},...,u_{m-1}\quad )} et {(v_{1},...,v_{n-1}\quad ),} alors {w=} {(w_{0},...,w_{p})} est une plssc de {u=(u_{0},...,u_{m-1}\quad )} et {v=(v_{0},...,v_{n-1}\quad ).}
- Si {u_{0}\ne v_{0},} si {w^{\prime }} est une plssc de {(u_{1},...,u_{m-1}\quad )} et {v,} et si {w^{\prime \prime }} est une plssc de {u} et {(v_{1},...,v_{n-1}\quad ),} alors (en notant {w} la plus longue de {w^{\prime }} et {w^{\prime \prime },} et l’une quelconque des deux si elles sont de même longueur{),w} est une plssc de {u} et {v.}
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres