<p>I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.</p>

<p>Let's say we have two ordered lists of symbols (strings):</p>

<pre><code>A = "foobarquuz123foo"
B = "foobar456quuzfoo"
</code></pre>

<p>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:</p>

<pre><code>C = "foobar456quuz123foo"
</code></pre>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>I would be very happy to get also suggestions for books that illustrate this and similar problems.</p>

CC BY-SA 3.0
2014-09-03T16:51:40.913Z
I believe you're looking for the shortest common supersequence problem.
bbejot
CC BY-SA 3.0
2014-09-04T06:47:45.480Z
As commented by bbejot, is the [Shortest Common Supersequence problem](http://en.wikipedia.org/wiki/Shortest_common_supersequence) what you need? (you can find a lot of works on the subject simply googling)
Marzio De Biasi
CC BY-SA 3.0
2014-09-04T08:19:45.620Z
@bbejot: yes, I think that this is the problem I was looking for. Thanks!
fstab
<ds.algorithms><sorting><string-matching><greedy-algorithms><string-search>
Algorithm to merge two incomplete sequences of symbols (strings) into a complete one
fstab
# Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

(Asked by: username_0 on 2014-09-03)

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.

**Tags:** ds.algorithms, sorting, string-matching, greedy-algorithms, string-search
> **Comments:**
> **username_1**: I believe you're looking for the shortest common supersequence problem.  
> **username_2**: As commented by bbejot, is the [Shortest Common Supersequence problem](http://en.wikipedia.org/wiki/Shortest_common_supersequence) what you need? (you can find a lot of works on the subject simply googling)  
> **username_0**: @bbejot: yes, I think that this is the problem I was looking for. Thanks!  

---

## 0 answers

