*longest common sub-sequence(LCS)*among them?

*is*“TAG”.

*LCS*of two strings. To understand the solution, let us walk through a simple example.

*if str1[n-1] = str2[m-1]*

*otherwise*LCS(“ACDG”,”CAG”) = LCS(“ACD”, “CA”) + “G”

LCS(“ACD”, “CA”) = Max( LCS(“AC”, “CA”), LCS(“ACD”,”C”) )

LCS(“ACD”, “C”) = Max( LCS(“AC”, “C”), LCS(“ACD”,””) )

and so on…

we can see that LCS(“ACD”,”CA”) is “C”; so “CG” is the final output.

If we implement this naive recursion, we repeat the calculation for many sub problems. For efficient implementation we use a 2 dimensional array of size (n+1)*(m+1).The table is calculated using the rules given below which directly follow from the recursive definition given above.

table[i][j]= 0

if either of the string is empty

= 1 + table[i-1][j-1] if their last characters are equal

= max(table[i-1][j], table[i][j-1]) otherwise

Here is an example table.

A 0 1 1 1 1 1 1

Here are the python implementations of both approaches.