LCS{Longest Common Subsequent}

 In LCS Problem we have given two sequence
and we wish to find maximum length common
subsequent of these two given sequence.

picture output example of lcs :-

PROGRAM:-

#include<stdio.h>
#include<conio.h>
#include<string.h>
void print_lcs(char b[10][10],char x[10],int i,int j)
{

if(i==0||j==0)
{
return;
}
if(b[i][j]=='*')
{
print_lcs(b,x,i-1,j-1);
printf("%c",x[i-1]);
}
else if(b[i][j]=='|')
{
print_lcs(b,x,i-1,j);
}
else
{
print_lcs(b,x,i,j-1);
}

}
void main()
{
char x[10],y[10],b[10][10];
int i,j,m,n,c[10][10];
clrscr();
printf("************enter the first string*************\n");
scanf("%s",&x);
m=strlen(x);
printf("************enter the second string************\n");
scanf("%s",&y);
n=strlen(y);
printf("length of the first string is=\t%d\nlength of second string is=\t%d\n\n\n",m,n);
for(j=0;j<=n;j++)
{
c[0][j]=0;
}
for(i=0;i<=m;i++)
{
c[i][0]=0;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
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("THE SOLUTION TO THE LCS PROBLEM IS=");
print_lcs(b,x,m,n);

printf("\n\nAND IT CAN BE OBTAINED AS FOLLOWS\n\n");
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{

printf("%d%c",c[i][j],b[i][j]);
printf("\t");
}
printf("\n");
}
printf("\n");
printf("* = diagonal\n");
printf("| = up\n");
printf("- = side");
getch();
}