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