#include <iostream>
#include <cstring>
using namespace std;
int mem[100][100];
int max(int a, int b)
{
return (a>b)?a:b;
}
int lcs(char* s, char* t, int i, int j)
{
if(i<0 || j<0)
return 0;
if(mem[i][j] != -1)
return mem[i][j];
if(s[i] != t[j])
{
mem[i][j] = max(lcs(s,t,i-1,j), lcs(s,t,i,j-1));
}
else
{
mem[i][j] = 1 + lcs(s,t,i-1,j-1);
}
return mem[i][j];
}
int main() {
// your code goes here
char s[] = "thsi is a bir senrence to find eit distance";
char t[] = "this is a big sentence to find edit distance";
memset(mem, -1, sizeof(mem));
int len = lcs(s,t,strlen(s)-1, strlen(t)-1);
cout << "length of longest common subsequence between <"<<s<<"> and <" << t << "> is " << len;
return 0;
}
Output:
length of longest common subsequence between <thsi is a bir senrence to find eit distance> and <this is a big sentence to find edit distance> is 40
+++++++++++++++++++++++
using dynamic programming
+++++++++++++++++++++++
#include <iostream>
#include <cstring>
using namespace std;
//longest common subsequence between 2 strings
int mem[20][20];
int max(int a, int b) { return a>b?a:b; }
int lcs(char s1[], int l1, char s2[], int l2)
{
int len = 0;
if(mem[l1][l2] != -1)
return mem[l1][l2];
for(int i=0; i<l1; i++)
{
for(int j=0; j<l2; j++)
{
if(s1[i] == s2[j])
{
mem[i][j] = (i>0 && j>0)?1+ mem[i-1][j-1]:1;
}
else
{
mem[i][j] = max((j>0)?mem[i][j-1]:0, (i>0)?mem[i-1][j]:0);
}
}
}
return mem[l1-1][l2-1];
}
int main() {
// your code goes here
memset(mem, -1, sizeof(mem));
char a[] = "subsequence";
char b[] = "queue";
int len = lcs(a,strlen(a), b, strlen(b));
cout << "LCS between " << a << " and " << b << " is=" << len;
return 0;
}
