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.
The problem is called shortest common supersequence. For an arbitrary number of strings it is NP-hard, but for two strings it can be solved efficiently:

First find the longest common subsequence of the two strings with dynamic programming, then insert the remaining characters.