#include<stdio.h>
#include<string.h>
char **b;
void print(char *x,int m,int n)
{
if(m==0||n==0)
return;
if(b[m][n]=='!')
{
print(x,m-1,n-1);
printf("%c",x[m-1]);
}
else if(b[m][n]=='@')
print(x,m-1,n);
else
print(x,m,n-1);
}
void lcs(char *x,char *y)
{
int m,n,**c,i,j;
m=strlen(x);
n=strlen(y);
c=(int **)malloc((m+1)*sizeof(int *));
for(i=0;i<m+1;i++)
c[i]=(int *)malloc((n+1)*sizeof(int));
b=(char **)malloc((m+1)*sizeof(char *));
for(i=0;i<m+1;i++)
b[i]=(char *)malloc((n+1)*sizeof(char));
for(i=0;i<m;i++)
{
c[i][0]=0;
b[i][0]=0;
}
for(i=0;i<n;i++)
{
c[0][i]=0;
b[0][i]=0;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(x[i]==y[j])
{
c[i+1][j+1]=c[i][j]+1;
b[i+1][j+1]='!';
}
else if(c[i][j+1]>=c[i+1][j])
{
c[i+1][j+1]=c[i][j+1];
b[i+1][j+1]='@';
}
else
{
c[i+1][j+1]=c[i+1][j];
b[i+1][j+1]='#';
}
}
}
printf("\nLength of LCS=%d\nSubsequence is\n",c[m][n]);
print(x,m,n);
printf("\n");
}
int main()
{
int i,j;
char x[50],y[50];
system("clear");
printf("Enter first sequence\n");
scanf("%s",&x);
printf("Enter second sequence\n");
scanf("%s",&y);
lcs(x,y);
}
No comments:
Post a Comment