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.

  • 12
    $\begingroup$ I believe you're looking for the shortest common supersequence problem. $\endgroup$ – bbejot Sep 3 '14 at 16:51
  • 3
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Sep 4 '14 at 6:47
  • $\begingroup$ @bbejot: yes, I think that this is the problem I was looking for. Thanks! $\endgroup$ – fstab Sep 4 '14 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.