by This problem can be solved using multiple approaches but here we will solve this problem using Dynamic Programming and showcase how dynamic programming will make the execution super-fast.
We will go through with the same steps as mentioned in Dynamic Programming post to tackle this problem step by step for better understanding.
Let’s explain the problem,
The longest subsequence problem (LCS) is the problem in which we need to find the longest subsequence present in two sequences. In this case, characters doesn’t require to be in consecutive places.
For eg:
LCS for sequence “ABCDFG” and “ABCGDFG” is “ABCDFG” and its length is 6.
Let’s apply the 3 Steps rule (Dynamic Programming) to tackle this problem.
- Break the problem into smaller sub problem.
Let’s assume Li,j is the length of LCS for string X1…i and Y1…i
- Solve the Problem using Recursion
If Xi == Yj then this should be treated as a valid subsequences. So, in this case the equation would become something like:
Li,j = Li-1,j-1 + 1
- Use smaller problems results to solve the bigger complex problem.
As we know,
L0,0 = 0
Li,0 = 0
L0,j = 0
Now let’s compare the result in terms of execution time for both recursion and DP approach for solving the above problem.
#include <unistd.h>
#include <iostream>
#include <chrono>
#include <string.h>
using namespace std::chrono;
#define MAX_STRING_LENGTH 30
static long int loop = 0;
int lcs_using_recursion (char *str_a, char *str_b)
{
int val = 0;
loop++;
if (*str_a == '\0' || *str_b == '\0')
{
return 0;
}
if (*str_a == *str_b)
val++;
int ret1 = lcs_using_recursion (str_a, str_b+1);
int ret2 = lcs_using_recursion (str_a+1, str_b);
if (ret1 > ret2)
{
return (val + ret1);
}
else
{
return (val + ret2);
}
}
int LCS[MAX_STRING_LENGTH][MAX_STRING_LENGTH] = {0};
void lcs_using_dp (char *str_a, char *str_b, int len_a, int len_b)
{
for (int i = 1; i <= len_a; i++)
{
for (int j = 1; j <= len_b; j++)
{
if (str_a[i-1] == str_b[j-1])
{
LCS[i][j] = LCS[i-1][j-1] + 1;
}
else
{
LCS[i][j] = (LCS[i-1][j] > LCS[i][j-1]) ? LCS[i-1][j] : LCS[i][j-1];
}
}
}
}
int main ()
{
char string_a[MAX_STRING_LENGTH];
char string_b[MAX_STRING_LENGTH];
printf ("Enter string a \n");
scanf ("%s", string_a);
printf ("enter string b \n");
scanf ("%s", string_b);
printf ("Entered strings are %s and %s \n", string_a, string_b);
high_resolution_clock::time_point t1 = high_resolution_clock::now();
int max_lcs_using_recursion = lcs_using_recursion (string_a, string_b);
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto recDuration = duration_cast<microseconds>( t2 - t1 ).count();
printf ("LCS using recursion %d, time taken: %ld microseconds loop: %ld \n", max_lcs_using_recursion, recDuration, loop);
high_resolution_clock::time_point t3 = high_resolution_clock::now();
int max_lcs_using_dp = 0;
LCS[0][0] = 0;
if (string_a[0] != '\0' && string_b[0] != '\0')
{
LCS[1][1] = string_a[0] == string_b[0] ? 1 : 0;
int len_a = strlen (string_a);
int len_b = strlen (string_b);
for (int i = 0; i <= len_a; i++)
{
LCS[i][0] = 0;
}
for (int i = 0; i <= len_b; i++)
{
LCS[0][i] = 0;
}
lcs_using_dp (string_a, string_b, len_a, len_b);
max_lcs_using_dp = LCS[len_a][len_b];
}
high_resolution_clock::time_point t4 = high_resolution_clock::now();
auto recDuration_dp = duration_cast<microseconds>( t4 - t3 ).count();
printf ("LCS using dp %d, time taken: %ld microseconds \n", max_lcs_using_dp, recDuration_dp);
}
Let’s take a pause and take a guess about How much faster DP approach would be compared to recursion ?
Ready for the results ?
Here it is
Enter string a
abcdfghjklijhy
enter string b
acbkcdfghopjkxlijhy
Entered strings are abcdfghjklijhy and acbkcdfghopjkxlijhy
LCS using recursion 14, time taken: 11514087 microseconds loop: 1637618399
LCS using dp 14, time taken: 8 microseconds
As you can see Dynamic programming is way way faster than conventional approach !!!!
