Shortest common supersequence Created 2026-10-20 Updated 2026-11-05
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.