title: Plus courte super-séquence commune
text: # Plus courte super-séquence commune
  
  En informatique théorique, et notamment en algorithmique des textes, le problème de la plus courte sur-séquence commune est un problème dual du problème de la plus longue sous-séquence commune. On trouve aussi l'anglicisme superséquence, mais la dénomination sur-séquence est plus logique en français par opposition à sous-séquence.
  
  ## Définition
  
  Étant donné deux suites de symboles X et Y, une suite U est une sur-séquence commune de X et Y si X et Y sont des sous-séquences (ou suites extraites) de U.
  
  Une plus courte sur-séquence commune est une sur-séquence de longueur minimale. Cette longueur est majorée par la somme des longueurs des deux séquences. Par exemple, si X=ab et Y=ba, les deux séquences U=aba et V=bab sont des sur-séquences communes de X et Y de longueur minimale. En général, et comme le montre l'exemple, une plus courte sur-séquence commune n'est pas unique.
  
  ## Algorithme
  
  Pour deux séquences d'entrée données, une plus courte sur-séquence commune peut être calculée facilement à partir d'une plus longue sous-séquence commune. Par exemple, pour X=abcbdab et Y=bdcaba, la plus longue sous-séquence commune est Z=bcba. En insérant les symboles de X=abcbdab et Y=bdcaba qui ne figurent pas dans Z tout en préservant l’ordre, on obtient U=abdcabdab. L'algorithme montre aussi que la longueur d'une plus courte sur-séquence commune est égale à la somme des deux longueurs diminuée de la longueur de la plus courte sous-séquence commune : |U|=|X|+|Y|-|Z|.
  
  ## Problèmes voisins
  
  Le problème plus général de trouver une chaîne de symboles S de longueur minimale qui est une sur-chaîne d'un ensemble de chaînes de symboles $S_1,S_2,...,S_l,$ c'est-à-dire telle que chaque $S_i$ est une sous-suite de S, est NP-complet. Il existe des algorithmes d'approximation bon en $moyenne^,.$
  
  