retagged by
3,698 views

1 Answer

1 votes
1 votes

X = " 0121301 " and Y = "132010"

Coming from the end of each string, last character are not matched,

So just ignore the last character in X or in Y.

LCS( X,Y) = MAX(   $\color{red}{LCS("0121301", "13201")}, \;\; \color{green}{LCS( "012130","132010")}\;\; )$

 

$\color{red}{LCS("0121301", "13201")}$ = LCS("01213", "132") + "01"

   LCS("01213", "132") = "13" or "12"

  ===> LCS("0121301", "13201") = "1301" or "1201"

 

$\color{green}{LCS( "012130","132010")}$ = LCS( "01213","13201") + "0"

  LCS( "01213","13201") = MAX(   $\color{blue}{LCS("0121", "13201")}, \;\; \color{violet}{LCS( "01213","1320")}\;\; )$

  $\color{blue}{LCS("0121", "13201")}$ = "121"

  $ \color{violet}{LCS( "01213","1320")}$ = "12" or "13"

  ===> LCS( "01213","13201") = "121"  ===> $\color{green}{LCS( "012130","132010")}$ = "1210"

 

∴ Length of LCS = 4

 

similar one https://gateoverflow.in/230069/made-easy-test-series

Answer:

Related questions

0 votes
0 votes
2 answers
1
Arjun asked Jan 2, 2019
4,323 views
Consider the graph shown below:Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is$17$$14$$16$$13$
0 votes
0 votes
1 answer
2
Arjun asked Jan 2, 2019
1,740 views
Match $\text{List I}$ with $\text{List II}$ and choose the correct answer from the code given below.$\begin{array} {clcl} & \textbf{List I} & & \textbf{List II} \\ & \...
0 votes
0 votes
0 answers
3
Arjun asked Jan 2, 2019
1,110 views
The second smallest of $n$ elements can be found with ____ comparisons in the worst case.$n-1$$\lg \: n$$n + ceil(\lg \: n)-2$$\frac{3n}{2}$