1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Sep 3, 2014 at 16:39
  • 3
    $\begingroup$ This looks like shortest common supersequence. $\endgroup$
    – FrankW
    Sep 3, 2014 at 16:42
  • $\begingroup$ 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". $\endgroup$
    – xavierm02
    Sep 3, 2014 at 16:53
  • $\begingroup$ @FrankW: Yes, this is what I was looking for. Thanks! $\endgroup$
    – fstab
    Sep 4, 2014 at 8:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.