﻿ Tips And Tutorial - Presented by Oneous!

Longest common subsequence (LCS)
Last Update: 6 June, 2009

Problem: The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). The DP solve of this problem only takes O(N*M) times where N and M is the length of two string.

My Code:

``````// // C++ code : LCS - Longest common subsequenc
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;
#define CLEAR(a) memset(a,0,sizeof(a))

class find_LCS
{
public:
char x[100],y[100],res[100];
int r,m,n,c[100][100],b[100][100];

find_LCS(char xx[],char yy[])
{
r=0;
strcpy(x,xx);
strcpy(y,yy);
m=strlen(x);
n=strlen(y);
CLEAR(c); // #define CLEAR(a) memset(a,0,sizeof(a)
}

int lcs()
{
int i,j;
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]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
return c[m][n];
}

void print_lcs(int i, int j)
{
if(i==0 || j==0)
return;
else if(b[i][j]==1)
{
print_lcs(i-1,j-1);
//	printf("%c",x[i-1])
res[r++]=x[i-1];
}
else if(b[i][j]==2)
{
print_lcs(i-1,j);
}
else
{
print_lcs(i,j-1);
}
}
void print_subseq(char st[])
{
print_lcs(m,n);
res[r]=NULL;
strcpy(st,res);
}
};

int main()
{
char inp1[100],inp2[100],result[100];
int val;

cout<<"Enter 2 line of string one by one"<<endl;
gets(inp1);
gets(inp2);

find_LCS obj(inp1,inp2);
val=obj.lcs();
printf("%d\n",val);
obj.print_subseq(result);
puts(result);

return 0;
}
``````