Implementation of Longest Common Subsequence problem

[Ritik]

In the implementation of a program to find the length of the longest common subsequence, could someone explain to me what does line 14 do?

void lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
 
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
 

[abhishekm71]

It simply checks, if the ith character in X is same as the jth character in Y, then it makes the value of L[i][j] to be 1 more than the value of L[i-1][j-1].

This is because whatever be the value of longest common subsequence upto [i-1][j-1], if you include one more character from X and Y, one more character gets included in the LCS.

[Ritik]

Got it! Thanks!