Longest Common Subsequence (Dynamic Programming)

Finding the length of Longest Common Subsequence (Dynamic Programming)

The top-down approach of the above program that prints the length of the longest common subsequence:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100 
int max(int a, int b);
 int tab[SIZE][SIZE]; // to store the results in table to avoid re-computation

int lcs( char *X, char *Y, int m, int n )
{
   if(tab[m][n]>-1)
      return tab[m][n];
   if (m == 0 || n == 0)
     return 0;
   if (X[m] == Y[n]){
     tab[m][n]= 1 + lcs(X, Y, m-1, n-1);
     }
   else
     tab[m][n]= max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
     
  return tab[m][n];   
}
 
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
int main()
{
  int i,j,len;
  char X[] = "398397970";
  char Y[] = "3399917206";
 
  int m = strlen(X);
  int n = strlen(Y);
  //int tab[m][n];
 for(i=0;i<=m;i++)
 for(j=i;j<=n;j++)
 tab[i][j]=-1;
 len=lcs(X,Y,m,n);
  printf("Length of LCS is %d\n", len);
  return 0;
}

To print the common subsequence along with the length.

Note: There can be multiple answers possible for this problem.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100 
int max(int a, int b);
 int tab[SIZE][SIZE]; // to store the results in table to avoid re-computation

int lcs( char *X, char *Y, int m, int n )
{
   if(tab[m][n]>-1)
      return tab[m][n];
   if (m == 0 || n == 0)
     return 0;
   if (X[m] == Y[n]){
     tab[m][n]= 1 + lcs(X, Y, m-1, n-1);
     }
   else
     tab[m][n]= max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
     
  return tab[m][n];   
}
 
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
int main()
{
  int i,j,len;
  char X[] = "398397970";
  char Y[] = "3399917206";
 
  int m = strlen(X);
  int n = strlen(Y);
  //int tab[m][n];
 for(i=0;i<=m;i++)
 for(j=i;j<=n;j++)
 tab[i][j]=-1;
 len=lcs(X,Y,m,n);
  printf("Length of LCS is %d\n", len);
  char lc[len+1];
  lc[len]='\0';
 i = m;j = n;
   while (i > 0 && j > 0)
   {
      if (X[i] == Y[j])
      {
          lc[len-1] = X[i-1]; 
          i--; j--; len--;     
      }
 
      else if (tab[i-1][j] > tab[i][j-1])
         i--;
      else
         j--;
   }
 printf("Longest Common Subsequence is: %s",lc);


  return 0;
}

Output: