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

Answer 1

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.

Answer 2

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);
}

Answer 3

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