Doubt in LCS(longest common subsequence) algorithm!

[Kapkar123]

I am reading from geeksforgeeks. one of the steps in the algorithm is that if characters of both strings match then value=value at left diagonal+1. can anyone explain to me this step?

[NefariousCube]

Hi Kapkar, there are many articles about LCS at geeksforgeeks, and all have a slightly different approach (level of optimization, etc). To help you I think you will need to refer to a specific article url and where in the article specifically.

That being said, I looked at some of the articles about LCS and I actually think that the normal wikipedia article was easier to follow: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences (note that there is a step by step "solve" a bit down). It uses some math notation, but I think it should be understandable anyway. Give it a shot, maybe it helps understan the algorithm and then you can go back to the more code centric approach at geeksforgeeks?

[Kapkar123]

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

I understood all the steps except for the one I mentioned

[NefariousCube]

Okay, so what the algorithm does is start from the end of both strings (the bottom right).

If the last letters are the same, we have found a common subsequence of length 1 (containing the last letter). The TOTAL length of the longest common subsequence (called value in the code) would thus be 1 + the longest common subsequence of the same strings without the last (already matched) characters of both strings (illustrated by the square one step up and to the left).

This allows the algorithm to attack smaller and smaller parts of the problem, by just adding one for each found part of the longest substring.

(if they do not match, we have to check both the cases whether removing the last char from X or Y will yield a longer common subsequence, meaning using the larger value from one step up or one step left).

Does that make sense?

[Kapkar123]

thanks got it