longest common subsequence

Question

For X=  BDCABA and Y=ABCBDAB find length of lcs and no of such  lcs..(solve it using table method)

Comments

3 sub- sequences of length 4: 

 BCAB , BCBA , BDAB

---

Can u explain ur approach..did u solve using table method or trial and error?

Answer 1

The length of LCS is 4

BCAB,BCBA,BDAB

This will help you as you requested in tabulation method.

https://www.youtube.com/watch?v=P-mMvhfJhu8

Answer 2

Given sequences are BDCABA & ABCBDAB.

ALGO:  

 LCS(m,n)

  {   1 + L(m-1,n-1)   if A[m] = B[n]         // if first character match then take it 

      max( LCS(m-1,n), LCS(m,n-1)  )   else   

  }

---

BDCABA & ABCBDAB : First character mismatch 

      then two cases   :

1)  BDCABA & BCBDAB : we hv removed Ist char from second string..

         Here Ist character match, 

 LCS = 1+ LCS( DCABA & CBDAB)

                    Now D & C mismatch again take two(can apply algo)..

              Here to do quickly we observe manually that longest possible now is 3 characters(we can use algo also..) - So, i get  CAB ,CBA,DAB  

which when combined with B gives BCAB,BCBA,BDAB

---

2)   DCABA & ABCBDAB :  Here we hv removed first B from Ist sequence

                            Now, D & A first characters again mismatch.

   two parts again:

          2a) CABA & ABCBDAB : no common subsequence of length 4 possible here

          2b) DCABA & BCBDAB : similarly here too - no possibility for a subsequence

                                                   of length 4