GATE CSE 2014 Set 2 | Question: 37

Question

Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___.

Comments

LCS of length 4 ==> x=4

LCS={qpqr,qprr,pqrr} ==>y=3

x+4y=34.

Answer 1

Answer is $34$.

In first string, if we want to get $4$ as maximum length then LCS should end with either "$rr$" or "$qr$".
Only $4$ combinations are possible for LCS with length $4$:

"$qpqr$", "$qqrr$","$pqrr$","$qprr$"

Now, check for matching sequences in second string, except for "$qqrr$" all are possible.

Comments

plz clearify

Here in question it is explicitly mentioned (Not necessarily Contiguous) but if Only Longest Common Subsequence is mentioned what should be our approach?Will it be same???

---

What made u think the LCS should end with either rr or qr ? Any logic ? Also why did u start considering 4 in the first place ??Couldn't understand your logic

---

I have tried to code it. If there some bug, plz let me know or fix it.
https://ideone.com/AV0kkF

Answer 2

I hope this helps. :)

Comments

5th row and 6th column has two arrows which is wrong. Two arrows are possible only in case where we need to consider the previous adjacent cells but not previous diagonal cell. There will always be only one arrow in case of diagonal case.

---

any easier method to find number of such sequences apart from this?

---

@Abhineet Singh This is the easiest method. 

Answer 3

Its a big problem if we solve it with DP or recursion.So we should use some intuition to get answer.

A=5 length and B= 7 length.

Maximum x can be 5 but 5 is not possible so try with 4 and we can easily find that 4 is satisfying for x.Now we need to find y.Here we know x=4 ,so let us write all the 4 length subsequences of A.As A is 5 length and we need 4 length so remove 1 character at a time and get the subsequence.

1. qpqr

2.qpqr

3.aprr

4.qqrr

5.pqrr

Now look for these in B and we will see except qqrr all are satisfying.So y=4 ,but 1 and 2 are same ,so y=3.

Now x+10y=34

Comments

Thanks rahul sharma 5 for such a nice approach

---

There is $qprr$ in place of $aprr$ @rahul sharma 5

---

Here it's working because we had to select subsequences of length 4 from a total of 5. If we had to select 4 out of 6, there'd have been 15 possibilities.

Answer 4

$\text{Step 1}:$ $LCS(i,j)$ depends on $LCS(i+1,j+1)$ when match else $max\{ LCS(i+1,j)\space and\space LCS(i,j+1)\}$

$\text{Step 1}:$ Starts at $LCS(m,n)$ and fill by row,column or diagonal 

$\text{Step 1}:$ When there is match then value of that cell $1+ LCS(i+1,j+1)$  else $\text{Step 1}$

                                          

Black Arrow - Fill columns and other arrow for backtracking 

so $x= 4 $and $y = 3 $

$x+10y = 4+10 * 3 = 34 $

Reference: - https://www.youtube.com/watch?v=xdA41xLxwuM&index=46&list=PLGdMwVKbjVQ8Ew7KUp65sRL9_k2_3xlKE

Comments

$pqrr,qpqr,qprr$ are three strings acc to figure