0
$\begingroup$

We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this problem?

For example, if $a=1011$ and $b=0100$, the minimal string that include both: $c=101100$. As you can see string $c$ includes both $a$ and $b$ (with the characters of $a$ appearing in the same order in $c$, possibly with other characters interspersed, and the same for $b$).

I think it can be solved by a dynamic programming algorithm.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This problem has been studied under the name shortest common supersequence. $\endgroup$
    – Raphael
    Commented Jun 16, 2015 at 11:33
  • $\begingroup$ What have you tried? Where did you get stuck? You think it can be solved by dynamic programming; well, what dynamic programming algorithms did you come up with? Did you come up with a recursive relation? We want to help you understand concepts, not solve exercise problems for you. $\endgroup$
    – D.W. ♦
    Commented Jun 17, 2015 at 6:16

2 Answers 2

Reset to default
3
$\begingroup$

Following the explanation on Wikipedia,

Note that the result of neither step is necessarily unique.

Writing actual (pseudo)code, correctness proof and runtime analysis are easy exercises.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ shouldn't that be shortest common supersequence? (like you suggest in your comment at the question) $\endgroup$
    – Hendrik Jan
    Commented Jun 16, 2015 at 12:49
  • $\begingroup$ Thank you, but: 1. Can you explain me this - "insert the characters which are not part of the LCS in-order and in appropriate positions." please? 2. There is clearer explanation for the LCS, because what wrote at Wikipedia is unclear... $\endgroup$
    – Yoar
    Commented Jun 16, 2015 at 12:53
  • $\begingroup$ @HendrikJan Yes. The OP looks for SCS, the algorithm gets there via an LCS. $\endgroup$
    – Raphael
    Commented Jun 16, 2015 at 13:51
  • $\begingroup$ @Yoar No, I won't. To be blunt, I think that the descriptions on Wikipedia are clear enough assuming you want to invest any time and thought yourself. I have no interest in helping you if all you want is code. $\endgroup$
    – Raphael
    Commented Jun 16, 2015 at 13:52
  • 1
    $\begingroup$ @Yoar It's explained with an example in the SCS article on Wikipedia. Say you have $a_1 \dots a_n$ as one sequence and $a_{i_1} \dots a_{i_k}$ with $k \leq n$ the LCS, you'll have to add $a_1 \dots a_{i_1-1}$, $a_{i_1+1}\dots a_{i_2 - 1}$, and so on in order to get an SCS. Similarly for $b$. Since $a_{i_x} = b_{j_x}$ for all $x \in [1..k]$ you can shuffle the parts between the characters of the LCS -- which are unequal, otherwise it would not be an LCS -- however you want. $\endgroup$
    – Raphael
    Commented Jun 16, 2015 at 15:02
1
$\begingroup$

Hint: assume $a$ starts with a 1st letter $x$, hence is some $xa'$. Similarly, assume $b$ is some $yb'$.

Now what is the shortest word that contains $a$ and $b$ when $x=y$ (when $a$ and $b$ start with the same char)? And what if $x\not=y$? Finally, what if $a$ is the empty word $\epsilon$? Or if $b$ is $\epsilon$?

Solving all these cases will lead you to a dynamic programming solution.

PS: what you call "a string $s$ that includes all characters of $a$" is formally called a supersequence. Write it $a\leq s$. In particular, the number of occurrences of the symbols in $a$ and their left-to-right order must be accounted for in $s$ but not necessarily at contiguous positions.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I still don't understand - I made few examples with the hind that you gave my but I still stuck... What with the 2nd letter (of $a$ and $b$)? What I do with it? Thank you! $\endgroup$
    – Yoar
    Commented Jun 16, 2015 at 10:38
  • $\begingroup$ And if I have $xx$, $yy$ at some place at a and b, what I need to do? $\endgroup$
    – Yoar
    Commented Jun 16, 2015 at 10:42
  • 1
    $\begingroup$ When you look at $a=xa'$ and $b=yb'$ with $x\not=y$ you may either go for $xs$ where $s$ is a supersequence of $a'$ and $b$ or for $yt$ where $t$ is a supersequence of $a$ of $b'$. Compute $s$ and $t$ and see which is shorter. $\endgroup$
    – phs
    Commented Jun 16, 2015 at 12:12
  • $\begingroup$ If you can explain little bit more it will be great!! Thank you!! $\endgroup$
    – Yoar
    Commented Jun 16, 2015 at 13:14
  • 1
    $\begingroup$ Run my explanations on an example. Take $a=$ TROLL and $b=$ LOL. What do you get? $\endgroup$
    – phs
    Commented Jun 17, 2015 at 7:40

Your Answer

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

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