Find Longest Common Subsequence Using Dynamic Programming In C

#include< stdio.h >
#include< stdio.h>
#include< conio.h>

#include< string.h>
#define MAX 50
int c[MAX][MAX];
char b[MAX][MAX];
char str1[MAX],str2[MAX];
char x[MAX],y[MAX],ans[MAX];
int m,n,ind;
void LCS(char x[MAX],char y[MAX]);
void printLCS(char[MAX][MAX],char[MAX],int,int);

void main()
{
 int i,j,ind1=1;
 clrscr();
 printf("\n Enter string1:");
 scanf("%s",&str1);
 printf("\n Enter string2:");
 scanf("%s",&str2);
 LCS(str1,str2);


 printf("\n All the possible Longest Common Subsequence(LCS):");
 printf("\n--------------------------------------------------------------");
 for(i=n;i>0;i--)
 {
   if(c[m][i]==c[m][n])
   {
    ind=0;
    printLCS(b,x,m,i);

    printf("\n solution %d: %s",ind1++,strrev(ans));
   }
   else
   {
    break;
   }

 }
 printf("\n--------------------------------------------------------------");

getch();

}
void LCS(char x1[MAX],char y1[MAX])
{
 int i,j;

 m=strlen(x1);
 n=strlen(y1);

 //------use to shift one character bcs index start from 1
 for(i=1;i<= m;i++)
 {
  x[i]=x1[i-1];
 }

 for(j=1;j<=n ;j++)
 {
  y[j]=y1[j-1];
 }
 //------end-------------------

 for(i=0;i<= m;i++)
  c[i][0]=0;

 for(j=0;j <= n;j++)
  c[0][j]=0;

 for(i=1;i<= m;i++)
 {
  for(j=1;j<= n;j++)
  {
   if(x[i]==y[j])
   {
    c[i][j]=c[i-1][j-1]+1;
    b[i][j]='\\';
   }
   else if(c[i-1][j] >=c[i][j-1])
   {
    c[i][j]=c[i-1][j];
    b[i][j]='|';
   }
   else
   {
    c[i][j]=c[i][j-1];
    b[i][j]='-';
   }
  }
 }
 printf("\n         ");;
 for(i=1;i<= n;i++)
  printf("   %3c",y[i]);

 printf("\n--------------------------------------------------------------");
 for(i=0;i<= m;i++)
 {
  printf("\n%1c |",x[i]);
  for(j=0;j<= n;j++)
  {
   printf("   %d %c",c[i][j],b[i][j]);
  }
 }
 printf("\n--------------------------------------------------------------");

}

void printLCS(char b[MAX][MAX],char x[MAX],int i,int j)
{
 if(i==0 || j==0)
 {
  //Exit
 }
 else if(b[i][j]=='\\')
 {
  ans[ind++]=x[i];
  printLCS(b,x,i-1,j-1);
 }
 else if(b[i][j]=='|')
  printLCS(b,x,i-1,j);
 else
  printLCS(b,x,i,j-1);

}

OUTPUT



Enter string1:ABCBDAB

 Enter string2:BDCABA

              B      D     C     A      B      A
 --------------------------------------------------------------
   |    0     0      0      0     0      0      0
 A |   0     0 |    0 |    0 |    1 \    1 -    1 \
 B |   0     1 \    1 -    1 -    1 |    2 \    2 -
 C |   0     1 |    1 |    2 \    2 -    2 |    2 |
 B |   0     1 \    1 |    2 |    2 |    3 \    3 -
 D |   0     1 |    2 \    2 |    2 |    3 |    3 |
 A |   0     1 |    2 |    2 |    3 \    3 |    4 \
 B |   0     1 \    2 |    2 |    3 |    4 \    4 |
 --------------------------------------------------------------
  All the possible Longest Common Subsequence(LCS):
 --------------------------------------------------------------
  solution 1: BCBA
  solution 2: BCAB
 --------------------------------------------------------------