# Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.

Let's say we have two ordered lists of symbols (strings):

A = "foobarquuz123foo"
B = "foobar456quuzfoo"


my goal is to have an algorithm that merges the two incomplete lists into the following, that can be considered completed, having parts from both lists:

C = "foobar456quuz123foo"


As you can see there is no intrinsic "sorting value" associated to the symbols, only their position, which is just a relative measure. Moreover, the symbols might be also repeated in arbitrary points of the strings.

Maybe the algorithm I am looking for might have been used in bioinformatics, for example for DNA or protein sequence alignment, but I am no expert of this.

What would you recommend? Do you have some pointers to algorithms that may solve this problem? I think that someone should already have figured out a solution with upper-bound computational complexity $O(k(n+m))$ where $k$ is a constant and $n$ and $m$ are the lengths of the strings.

I would be very happy to get also suggestions for books that illustrate this and similar problems.

• I believe you're looking for the shortest common supersequence problem. – bbejot Sep 3 '14 at 16:51
• As commented by bbejot, is the Shortest Common Supersequence problem what you need? (you can find a lot of works on the subject simply googling) – Marzio De Biasi Sep 4 '14 at 6:47
• @bbejot: yes, I think that this is the problem I was looking for. Thanks! – fstab Sep 4 '14 at 8:19