Plus courte super-séquence commune
# 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^,.$

