Finding Longest Common Sub-sequence > C Program

Analysis of Algorithm

Finding Longest Common Sub-sequence > C Program

#include<stdio.h>
#include<conio.h>
#include<string.h>
char b[20][20];
int c[20][20];
int m,n;
void lcs(char x[],char y[])
{

int i,j;
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]='/';//d for diagonal
}
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]='-';

}

}
void main()
{
char x[20];
char y[20];
char p[20],q[20];
char ans[20];
int index=19;
int i,j;
clrscr();
printf("Enter first string: ");
gets(x);
printf("Enter second string: ");
gets(y);
m= strlen(x);
n = strlen(y);
for(i=1;i<=m;i++)
p[i]=x[i-1];
for(j=1;j<=n;j++)
q[j]=y[j-1];


lcs(p,q);
printf("Cost matrix:\n");
for(i=0;i<=m;i++)
{ for(j=0;j<=n;j++)
printf("%d\t",c[i][j]);
printf("\n");

}
printf("Direction:\n");
for(i=1;i<=m;i++)
{ for(j=1;j<=n;j++)
printf("%c\t",b[i][j]);
printf("\n");

}
printf("Longest common subsequence: ");
for(i=m,j=n;i>0,j>0;)
{
if(b[i][j]=='/')
{
ans[index--]=p[i];
i-=1;
j-=1;
}
else if(b[i][j]=='|')
i-=1;
else
j-=1;
}
for(i=index+1;i<=19;i++)
printf("%c",ans[i]);

getch();

}


/*
Enter first string: ABCBDAB
Enter second string: BDCABA
Cost matrix:
0       0       0       0       0       0       0
0       0       0       0       1       1       1
0       1       1       1       1       2       2
0       1       1       2       2       2       2
0       1       1       2       2       3       3
0       1       2       2       2       3       3
0       1       2       2       3       3       4
0       1       2       2       3       4       4
Direction:
|       |       |       /       -       /
/       -       -       |       /       -
|       |       /       -       |       |
/       |       |       |       /       -
|       /       |       |       |       |
|       |       |       /       |       /
/       |       |       |       /       |
Longest common subsequence: BCBA

*/