Longest Common Subsequence

codingmadesimple

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int printlcs(char b[30][30],char x[], int m, int n)
{
if((m==0)||(n==0))
{
return 0;
}
if(b[m][n]==’*’)
{
cout<<“TEST”;
printlcs(b,x,m-1,n);
cout<<x[m];
}
else
{
cout<<“TEST”;
if(b[m][n]==’^’)
{
printlcs(b,x,m-1,n);
}
else
{
cout<<“test”;
printlcs(b,x,m,n-1);
}
}
}
void main()
{
clrscr();
char x[30], y[30],c[30][30],b[30][30];
int m,n;
cout<<“enter the length of strings”;
cin>>m>>n;
cout<<“enter string1”;
gets(x);
fflush(stdin);
cout<<“enter string 2”;
gets(y);
fflush(stdin);
for(int i=0;i<m;i++)
{
c[i][0]=0;
}
for(int 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][j]=c[i-1][j-1]+1;
b[i][j]=’*’;
}
else
{
if((c[i-1][j]>c[i][j-1])||(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]='<‘;
}
}
}
}
int h;
h=printlcs(b,x,m,n);
getch();
}

 

Theory:

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

View original post

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s