Longest common subsequence Algo

Question

In Longest Common Subsequence (LCS) Problem, why do we match last chars for the string. For ex Consider the input strings “AGGTAB” and “AXTXAYB”. Last characters match for the strings. So length of LCS can be written as:

L(“AGGTAB”, “AXTXAYB”) = 1 + L(“AGGTA”, “AXTXAY”)

Wouldn't the algo still produce the optimal search if we match first chars for string. For example

Consider the input strings “AGGTAB” and “AXTXAYB”. First characters match for the strings. So length of LCS can be written as:

L(“AGGTAB”, “AXTXAYB”) = 1 + L(“GGTAB”, “XTXAYB”)

LCS problem : Longest Common Subsequence Problem

Sergey Kalinichenko · Accepted Answer · 2014-05-15 19:17:07Z

2

Yes, this is the same thing.

Computing the LCS of two reversed sequences is the same as reversing the LCS of two sequences before reversal. In other words,

REVERSE(LCS(A,B)) = LCS(REVERSE(A), REVERSE(B))

Assuming that the LCS reduces from the end, the operation on the right would go from the opposite end, but achieve the same result.

That's why you can work with prefixes in the same way that they work with suffixes in the explanation: you would get the same kind of recursive reduction in the process.

Moreover, you can do reductions on both ends if you wish. However, this would complicate the algorithm a lot without giving you any speed up in return.

answered May 15, 2014 at 19:17

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

puneet Over a year ago

Thanks @dasblinkenlight for explaining it. I have seen people always use suffix part and was not sure why people are not using prefix.

Shreyansh Jain · Accepted Answer · 2018-02-11 12:56:28Z

1

Well it turns out that you can directly make use of length variables (say M,N) in recursion provided by user if we perform LCS from last. On the other hand you will have to create extra variables if you do it from start index. That's the reason former method is considered as standard otherwise there is no complexity difference and everything is same.

LCS (M, N)
{
if(M==0 || N==0)
return 0;
elseif (a[M]!=b[N])
return max(LCS(M,N-1), LCS(M-1,N));
else
return 1 + LCS(M-1,N-1);
}

answered Feb 11, 2018 at 12:56

Shreyansh Jain

1208 bronze badges

Comments

nikhil_vyas · Accepted Answer · 2014-05-15 19:14:52Z

0

Yes you could do that it will not change the time complexity. Starting from last is just a matter of convention.

answered May 15, 2014 at 19:14

nikhil_vyas

5531 gold badge5 silver badges17 bronze badges

Collectives™ on Stack Overflow

Longest common subsequence Algo

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related