Shortest Common Supersequence

The shortest common supersequence of two sequences X and Y is the shortest sequence that has both X and Y as subsequences; such a supersequence is not unique in general. For two sequences it can be constructed from their longest common subsequence, since the lengths satisfy L + S = m + n, where L is the length of the longest common subsequence, S is the length of the shortest common supersequence, and m and n are the lengths of the two input sequences. For more than two sequences, both the shortest-common-supersequence and longest-common-subsequence problems can be solved by dynamic programming in O(n^k) time for k sequences of maximum length n, but the general problem with an arbitrary number of input sequences is NP-hard. A related but distinct problem, the shortest common superstring, asks for the shortest string containing every string in a given finite set as a contiguous substring rather than merely a subsequence; it is also NP-hard and APX-complete, with known approximation algorithms achieving an approximation factor of 2.475. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/