Using ANSI/ISO C++ write a program that: In this programming exercise you will i

Question

Using ANSI/ISO C++ write a program that:

In this programming exercise you will implement the algorithm we developed in class for solving the Longest Common Subsequence problem.

prompts the user to enter a pair of strings

displays the LCS table produced by the algorithm

displays the longest common subsequence found

allows the user to repeat the process with a new pair of strings

Your program should create the two dimensional array for the LCS table after getting the strings from the user.

(If you are programming in C++, be sure to de-allocate your array before repeating the process.)

Explanation / Answer

// C++ code
#include <iostream>
#include <cmath>
#include <math.h>
#include <fstream>

using namespace std;

int max(int n1, int n2)
{
if(n1 > n2)
return n1;
else
return n2;
}

int longestCommonsubsqs(string s1, string s2)
{

int l1 = s1.size();
int l2 = s2.size();
int lcsMatrix[l1+1][l2+1];

for (int i=0; i<=l1; i++)
{
for (int j=0; j<=l2; j++)
{
if (i == 0 || j == 0)
lcsMatrix[i][j] = 0;

else if (s1[i-1] == s2[j-1])
lcsMatrix[i][j] = lcsMatrix[i-1][j-1] + 1;

else
lcsMatrix[i][j] = max(lcsMatrix[i-1][j], lcsMatrix[i][j-1]);
}
}
  
return lcsMatrix[l1][l2];
}

int main()
{
string s1;
string s2;

cout << "Enter string1: ";
cin >> s1;
cout << "Enter string2: ";
cin >> s2;

cout << "Length of longest Common subsequence : " << longestCommonsubsqs(s1,s2) << endl;

return 0;
}

/*
output:

Enter string1: hanumanchalisa
Enter string2: clasilahanumna
Length of longest Common subsequence : 7

*/

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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