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.