A C++ program that uses dynamic programming to find the longest common subsequen

Question

A C++ program that uses dynamic programming to find the longest common subsequence for two strings. The user should be able to enter two strings and the program should output the longest common substring and its length. For example:

Enter string 1: abcaccba

Enter string 2: bacabbac

Answer: The LCS "acaba" has a length of 5.

I have the program here which gives the right LCS output, but I'm not sure how to allow the user to input the strings instead of storing them as char X and char Y:

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

void lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];

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

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

if (i == 0 || j == 0)
L[i][j] = 0;

else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;

else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}

int index = L[m][n];

char lcs[index+1];
lcs[index] = '';

int i = m, j = n;
while (i > 0 && j > 0)
{

if (X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1];
i--; j--; index--;
}

else if (L[i-1][j] > L[i][j-1])
i--;

else
j--;
}

cout << "The LCS "<<lcs<<" has a length of "<<L[m][n]<<" ." << endl;
}

int main()
{
char X[] = "abcaccba";
char Y[] = "bacabbac";
int m = strlen(X);
int n = strlen(Y);
lcs(X, Y, m, n);
return 0;
}

Explanation / Answer

Solution:

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

void lcs( string X, string Y, int m, int n )
{
   int L[m+1][n+1];

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

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

       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   int index = L[m][n];

   char lcs[index+1];
   lcs[index] = '';

   int i = m, j = n;
   while (i > 0 && j > 0)
   {

      if (X[i-1] == Y[j-1])
      {
          lcs[index-1] = X[i-1];
          i--; j--; index--;
      }

      else if (L[i-1][j] > L[i][j-1])
         i--;

      else
         j--;
   }

   cout << "The LCS "<<lcs<<" has a length of "<<L[m][n]<<" ." << endl;
}

int main()
{
string X = "abcaccba";
string Y = "bacabbac";
int m = X.size();
int n = Y.size();
lcs(X, Y, m, n);
return 0;
}

This will produce same output.

_____________________________________________________________

<By Nancy>

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.