Test by Bikram | Algorithms | Test 2 | Question: 15

Question

The length of the longest common subsequence of $L = ( 1,0,0,1,0,1,0,1 )$ and  $K =( 0,1,0,1,1,0,1,1,0 )$ is __________.

Comments

@Bikram sir can you explain it.

---

@Shubham Aggarwal check it now .

---

010101

Answer 1

It might be helpful to solve LCS problem.

There are only three steps-

1)when either M=0 or N=0 means nothing to be match so value 0

2)From both string if matched then 1+LCS(M-1,N-1) means in table it will take value from (M-1,N-1)diagonal value +1.

3)no matching then it will take maximum value from either upper row element or immediate  left element.

Comments

@Prateek Raghuvanshi thanks bro for your valuable efforts. i have just little doubt now all are clear. again thanx

Answer 2

The longest sub sequences will be

101101

101010

 

both of them are of length 6.