Shortest common supersequence
This shortest common supersequence problem is closely related to the lcs (longest-common subsequence problem. Again, assume that two sequences X = < x1,...,xm > and Y = < y1,...,yn > are given.
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, a scs can be formed from a lcs easily. For example, if X and Y, the lcs is Z. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U.
![{\displaystyle [1..m]=abcbdab}](/media/api/rest_v1/media/math/render/svg/a81f42392c43a0b0298789a903338bf76dc97223)
![{\displaystyle [1..n]=bdcaba}](/media/api/rest_v1/media/math/render/svg/9c34a14553055e81f2d6a800b4b8a81818503a8b)
![{\displaystyle [1..r]=bcba}](/media/api/rest_v1/media/math/render/svg/3b3420b174001e3458f72cfd5121bfc789e03e67)
![{\displaystyle [1..t]=abdcabdab}](/media/api/rest_v1/media/math/render/svg/56442a3d6041f3395a6d3c705c0e4d391d5c9b63)
It is quite clear that for two input sequences. However, for three or more input sequences this does not hold. Note also, that the lcs and the csc problems are not dual problems.
