LONGEST COMMON SUBSEQUENCE for file

#include<iostream.h>

#include<conio.h>

#include<string.h>

#include<stdio.h>

#include<time.h>

#define max 12

void lcs_length(char[],char[],int,int);

void print_lcs(char[max][max],char[],int,int);

void main()

{

char x[10],y[10],ans ;

int i,j;

clrscr();

clock_t t1,t2;

t1=clock();

cout<<"\n Enter the first sequence(less than or equal to 10 characters";

gets(x);

i=strlen(x);

cout<<"\n enter the second sequence";

gets(y);

j=strlen(y);

lcs_length(x,y,i,j);

t2=clock();

cout<<"the time complexity"<<(t2-t1)/CLK_TCK;

getch();

}

void lcs_length(char x[10],char y[10],int m,int n)

{

int i,j;

int c[max][max];

char b[max][max];

for(i=0;i<max;i++)

for(j=0;j<max;j++)

b[i][j]='0';

for(i=1;i<=m;i++)

c[i][0]=0;

for(j=0;j<=n;j++)

c[0][j]=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]='-';

}

}

}

cout<<"the c matrix is:\n";

for(i=0;i<=m;i++)

{

for(j=0;j<=n;j++)

cout<<"\t"<<c[i][j];

cout<<"\n" ;

}

cout<<"the b matrix is:\n";

for(i=1;i<=m;i++)

{

for(j=1;j<=n;j++)

cout<<"\t" <<b[i][j] ;

cout<<"\n";

}

cout<<"\n the combined matrix c and b is\n";

for(i=0;i<=m;i++)

{

for(j=0;j<=n;j++)

{

if((i==0)||(j==0))

cout<<c[i][j] ;

else

cout<<b[i][j]<<c[i][j] ;

}

cout<<"\n" ;

}

cout<<"\n the length of the longest common subsequence is\n"<<c[m][n];

cout<<"\n the longest sequence is";

print_lcs(b,x,m,n);

}

void print_lcs(char b[max][max],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);

cout<<x[i-1];

}

else if(b[i][j]=='|')

print_lcs(b,x,i-1,j);

else

print_lcs(b,x,i,j-1);

}