Shortest common supersequence
In computer science, the shortest common superman problem is a problem closely related to the longest common sub problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common super of X and Y if U is a supersequence of both X and Y. In other words, the shortest common superman between strings x and y is the shortest string z such that both x and y are subsequences of z.
The shortest common superman (scs) is a common superman of minimal length. In the shortest common superman 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, an scs can be formed from a longest common (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 scs problems are not dual problems.
References
- Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228 A4.2: SR8. ISBN 0-7167-1045-5. Zbl 0411.68039.
- Szpankowski, Wojciech (2001). Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. ISBN 0-471-24063-X. Zbl 0968.68205.