# Algorithm to merge two incomplete lists 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 = "foobarquuz123"
B = "foobar456quuz"


my goal is to have a way to merge the two incomplete lists into the following, completed with parts from both:

C = "foobar456quuz123"


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.

• We need a more precise definition of what the problem statement is. You gave one example, but not a general specification of what output you want. If the input strings are $S$ and $T$, what do you want the output to be?
– D.W.
Sep 3, 2014 at 16:39
• This looks like shortest common supersequence. Sep 3, 2014 at 16:42
• In a way, you want something in the intersection of the languages containing all supersequences of each of your words. Since those languages are regular, you can compute their intersection. Then you just have to take a word in the resulting language. You might get the minimal length one if you avoid all "loops". Sep 3, 2014 at 16:53
• @FrankW: Yes, this is what I was looking for. Thanks! Sep 4, 2014 at 8:20