title: Plus longue sous-séquence commune
text: # Plus longue sous-séquence commune
  
  En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique.
  
  La généralisation à un nombre arbitraire de suites est un problème NP-difficile : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences.
  
  ## Exemple
  
  Pour les deux séquences de caractères suivantes :
  
  * « abcde »,
  * « ceij »,
  
  la plus longue sous-séquence commune est « ce ».
  
  Dans ce problème, il est nécessaire que les éléments communs soient dans le même ordre dans les différentes séquences, mais pas qu’ils soient obligatoirement consécutifs : « e » n’est pas consécutif à « c » dans la première séquence.
  
  ## Algorithme par force brute
  
  On constate par dénombrement qu'il existe $2^{n}$ sous-séquences pour une chaîne de longueur $n$. Les essayer toutes par force brute pour trouver la plus longue qui soit une sous-séquence d'une autre chaîne a donc une complexité exponentielle, ce qui n'est pas souhaitable en pratique.
  
  ## Résolution en temps polynomial pour deux suites
  
  Une telle sous-séquence peut être obtenue par un algorithme de programmation dynamique dont le temps d'exécution est proportionnel au produit des longueurs des deux séquences.
  
  ### Structure d'une solution
  
  Il est possible de ramener le problème de recherche de plus longue sous séquence commune (PLSC) entre deux chaînes données à une recherche entre deux chaînes de taille inférieure grâce au théorème suivant (où $X_{l}$ désigne les $l$ premiers caractères de la séquence $X$):
  
  Théorème — Soit $X=[x_{1},\dots ,x_{m}]$ et $Y=[y_{1},\dots ,y_{n}]$ deux séquences, et soit $Z=[z_{1},\dots ,z_{k}]$ une plus longue sous-séquence commune quelconque de $X$ et $Y$. On a alors :
  
  * Si $x_{m}=y_{n}$ alors $z_{k}=x_{m}=y_{n}$ et de plus $Z_{k-1}$ est une PLSC de $X_{m-1}$ et $Y_{n-1}$ ;
  * Si $x_{m}\neq y_{n}$ alors si $z_{k}\neq x_{m}$ on a $Z$ qui est une PLSC de $X_{m-1}$ et $Y$ ;
  * Si $x_{m}\neq y_{n}$ alors si $z_{k}\neq y_{n}$ on a $Z$ qui est une PLSC de $X$ et $Y_{n-1}$.
  
  Les trois cas $\left\langle x_{m}=y_{n}\right\rangle$, $\left\langle x_{m}\neq y_{n}~{\mathsf {ET}}~z_{k}\neq x_{m}\right\rangle$ et $\left\langle x_{m}\neq y_{n}~{\mathsf {ET}}~z_{k}\neq y_{n}\right\rangle$ sont exhaustifs, ce qui permet bien de se ramener à un problème de taille inférieure.
  
  ### Longueur des plus longues sous-séquences communes
  
  On crée un tableau à deux dimensions $c[1\cdot \cdot m][1\cdot \cdot n]$ dans lequel chaque case $c[i][j]$ est destiné à contenir la longueur des PLSCs entre $X_{i}$ et $Y_{j}$. On peut alors calculer de proche en proche $c[i][j]$ pour chaque couple d'indice $i$ et $j$. Du théorème précédent découle en effet la formule:
  
  $c[i][j]={\begin{cases}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},\\{\mathsf {max}}(c[i][j-1],c[i-1][j])&{\text{ si }}i,j>0{\text{ et }}x_{i}\neq y_{j}.\end{cases}}$
  
  Le calcul du contenu des cases de $c$ peut être effectué avec une complexité ${\mathcal {O}}(mn)$, car le contenu de chaque case est calculable à partir des cases précédente en ${\mathcal {O}}(1)$.
  
  ### Obtention d'une plus longue sous-séquence commune
  
  La formule précédente permet de calculer de proche en proche les cases de $c$. On peut reconstituer une plus longue sous-séquence commune grâce à lui.
  
  Pour cela on effectue un parcours depuis $c[m][n]$ suivant la règle suivante
  
  Depuis une case $c[i][j]$ de valeur $\alpha$:
  
  * Si $x_{i}=y_{j}$, on passe à la case $c[i-1][j-1]$ de valeur $\alpha -1$ et on ajoute ce caractère ($x_{i}=y_{j}$) au début de la PLSC en construction.
  * Si $x_{i}\neq y_{j}$,
     * Si $c[i][j-1]=c[i-1][j]=\alpha$, on passe indifféremment à la case $c[i-1][j]$ ou $c[i][j-1]$.
     * Si $c[i][j-1]=\alpha >c[i-1][j]$, on passe à la case $c[i][j-1]$
     * Si $c[i-1][j]=\alpha >c[i][j-1]$, on passe à la case $c[i-1][j]$
  
  Un exemple de parcours est donné par le tableau suivant, grâce auquel on déduit que MJAU est une plus longue sous-séquence commune à MZJAWXU et XMJYAUZ :
  
  | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
  | - | - | - | - | - | - | - | - | - | - |
  | | | Ø | M | Z | J | A | W | X | U |
  | 0 | Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  | 1 | X | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
  | 2 | M | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  | 3 | J | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
  | 4 | Y | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
  | 5 | A | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 |
  | 6 | U | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 |
  | 7 | Z | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
  
  ### Complexité de l'algorithme
  
  Le calcul du contenu des cases de $c$ peut être effectué avec une complexité ${\mathcal {O}}(mn)$, car le contenu de chaque case est calculable à partir des cases précédente en ${\mathcal {O}}(1)$.
  
  Une fois $c$ connu, l'obtention d'une PLSC a une complexité ${\mathcal {O}}(m+n)$.
  
  