A shortest common supersequence of two finite sequences is a shortest sequence containing each as a subsequence. Order is retained, but occurrences need not be contiguous. For and , is such a sequence; is another.
For lengths , its length is , where is the longest common subsequence length. Align a common subsequence of maximal length and merge the unmatched portions to prove the upper bound. Conversely, an alignment inside any common supersequence identifies at least shared positions when its length is , proving the lower bound. This formula is for two inputs; several inputs require a different analysis.

Articles by others on the same topic (1)

The Shortest Common Supersequence (SCS) of two sequences is the smallest sequence that contains both of the original sequences as subsequences. In other words, it's a sequence that can be derived from either of the original sequences by deleting zero or more elements, without rearranging the order of the remaining elements.