Shortest common supersequence

In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem 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 items can be removed from U to produce X or Y. In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem 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 items can be removed from U to produce X or Y. A 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, an SCS is not unique. For two input sequences, an SCS can be formed from a longest common subsequence (LCS) easily. For example, if X [ 1.. m ] = a b c b d a b {displaystyle =abcbdab} and Y [ 1.. n ] = b d c a b a {displaystyle =bdcaba} , the lcs is Z [ 1.. r ] = b c b a {displaystyle =bcba} . By inserting the non-lcs symbols while preserving the symbol order, we get the SCS: U [ 1.. t ] = a b d c a b d a b {displaystyle =abdcabdab} . It is quite clear that r + t = m + n {displaystyle 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. The closely related problem of finding a string which is a superstring of a finite set of strings S = { s1,s2,...,sn } is NP-Complete. Also, good (constant factor) approximations have been found for the average case but not for the worst case. However, it can be formulated as an instance of weighted set cover in such a way that the weight of the optimal solution to the set cover instance is less than twice the length of the shortest superstring S. One can then use the O(log(n))-approximation for weighted set-cover to obtain an O(log(n))-approximation for the shortest superstring (note that this is not a constant factor approximation). For any string x in this alphabet, define P(x) to be the set of all strings which are substrings of x. The instance I of set cover is formulated as follows: The instance I can then be solved using an algorithm for weighted set cover, and the algorithm can output an arbitrary concatenation of the strings x for which the weighted set cover algorithm outputs P(x). Consider the set S = { abc, cde, fab }, which becomes the universe of the weighted set cover instance. In this case, M = { abcde, fabc }. Then the set of subsets of the universe is