This program in C finds 2 Longest common subsequence of 2 given strings(say X and Y),entered without any space on the screen individually,altering X and Y strings.I compiled and executed this above program successfully in Dev Cpp compiler as a C file(not a c++ file).
Longest Common Subsequence
#include<stdio.h>
#include<conio.h>
#include<string.h>
void print_lcs(char b[][20],char x[],int i,int j)
{
if(i==0 || j==0)
return;
if(b[i][j]=='c')
{
print_lcs(b,x,i-1,j-1);
printf(" %c",x[i-1]);
}
else if(b[i][j]=='u')
print_lcs(b,x,i-1,j);
else
print_lcs(b,x,i,j-1);
}
void lcs_length(char x[],char y[])
{
int m,n,i,j,c[20][20];
char b[20][20];
m=strlen(x);
n=strlen(y);
for(i=0;i<=m;i++)
c[i][0]=0;
for(i=0;i<=n;i++)
c[0][i]=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]='c'; \\c stands for left upright cross
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]='u'; \\u stands for upright or above
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='l'; \\l stands for left
}
}
print_lcs(b,x,m,n);
}
void lcs()
{
int i,j;
char x[20],y[20];
printf("1st sequence:");
gets(x);
printf("2nd sequence:");
gets(y);
printf("\nlcs are:");
lcs_length(x,y);
printf("\n");
lcs_length(y,x);
}
main()
{
char ch;
do
{
lcs();
printf("\nContinue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='Y');
}
reenarankawat 0 Newbie Poster
Thank you so much, it was a great help.
terran1 0 Newbie Poster
Hi, could you please briefly describe the code? Like, which variable represent what (eg b, i, j...) and print_lcs, lcs_lenght - how to they work? i am confused and lost, thank a lot for a help....
reenarankawat4 0 Newbie Poster
#include<stdio.h>
#include<conio.h>
void print_lcs(char b[10][10],int x[10],int i,int j)
{
if(i==0||j==0)
{
return;
}
if(b[i][j]=='d')
{
print_lcs(b,x,i-1,j-1);
printf("%d",x[i-1]);
}
else
{
if(b[i][j]=='u')
{
print_lcs(b,x,i-1,j);
}
else
{
print_lcs(b,x,i,j-1);
}
}
}
void main()
{
int m,n,i,j,c[10][10],x[10],y[10];
char b[10][10];
clrscr();
printf("\n Enter the length of first array: ");
scanf("%d",&m);
printf("\n Enter %d elements: ",m);
for(i=0;i<m;i++)
{
scanf("%d",&x[i]);
}
printf("\n Enter the length of second array: ");
scanf("%d",&n);
printf("\n Enter %d elements :",n);
for(i=0;i<n;i++)
{
scanf("%d",&y[i]);
}
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-1]==y[j-1])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]='d';
}
else
{
if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]='u';
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='s';
}
}
}
}
printf("\n Matrix C is:\n");
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
printf("%d ",c[i][j]);
}
printf("\n");
}
printf("\n Matrix B is:\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf("%c ",b[i][j]);
}
printf("\n");
}
printf("\n The longest common subsequence is: ");
print_lcs(b,x,m,n);
getch();
}
m=holds length of first sequence.
n=holds length of second sequence.
x=name of first sequence array.
y=name of second sequence array.
c=a matrix of length of an LCS of the sequence x and y
If either i=0 or j=0, one of the sequences has length 0, so the LCS has length 0.
The optimal substructure of the LCS problem gives the recursive formula
c[i,j]= 0 ,if i=0 or j=0
= c[i-1,j-1]+1 ,if i,j>0 and x[ i ] = y[ j ]
= max( c[ i , j-1] , c[ i-1 , j]) ,if i,j>0 and x[ i ] != y[ j ]
It also maintains the table b[1..m , 1..n] to simplify construction of an optimal solution. Intuitively,
b[ i , j ] points to the table entry corresponding to the optimal subproblem solution chosen when compting c[ i , j ].
The procedure returns the b and c tables.
c[m , n] contains the length of an LCS of X and Y.
The function "print_lcs" is used to print the longest common subsequence pattern
terran1 0 Newbie Poster
Great, thank you very much. It helped me a lot...
hahahahohoho 0 Newbie Poster
thank you
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.