Definitions
Nearby Words

# Shortest common supersequence

This shortest common supersequence problem is closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if U is a supersequence of both X and Y.

The shortest common supersequence (scs) is a common supersequence of minimal length. In the shortest common supersequence problem, the two sequences X and Y are given and the task is to find a shortest possible common supersequence of these sequences. In general, the scs is not unique.

For two input sequences, an scs can be formed from an lcs easily. For example, if X$\left[1..m\right] = abcbdab$ and Y$\left[1..n\right] = bdcaba$, the lcs is Z$\left[1..r\right] = bcba$. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U$\left[1..t\right] = abdcabdab$.

It is quite clear that $r + t = m + n$ for two input sequences. However, for three or more input sequences this does not hold. Note also, that the lcs and the scs problems are not dual problems.