Answer to Question #285207 in C++ for tony

Question

Given two strings x and y, find the longest common subsequence and its length.

Sample Input 1:

x = “ABCBDAB”

y = “BDCABA”

Sample output 1:

longest common subsequence = “BCBA”

longest common subsequence length = 4 

Sample Input 2:

x = “ABBACQ”

y = “XAYZMBNNALQCTRQ”

Sample output 2:

longest common subsequence = “ABACQ”

longest common subsequence length = 5

Answer 1

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

int LCS(string x, string y,char* z)
{
	int n = x.size();
	int m = y.size();
	int** L=new int*[n+1];
	for (int i = 0; i<n+1; i++)
		L[i] = new int[m+1];
	int i, j;
	for (i = 0; i <= n; i++)
	{
		for(j=0;j<=m;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 res = L[n][m]; // length of longest common subsequence
	char* answer=new char[res+1]; // longest common subsequence
	i = n, j = m;
	answer[res] = '\0';
	while (i>0 && j>0)
	{
		if (x[i - 1] == y[j - 1])
		{
			answer[res - 1] = x[i - 1];
			i--; j--; res--;
		}
		else if (L[i - 1][j]>L[i][j - 1])
			i--;
		else
		{
			j--;
		}
	}
	for (int i = 0; i <= strlen(answer); i++)
	{
		z[i]=answer[i];
	}
	return L[n][m];
}

int main()
{
	string x = "ABCBDAB";
	string y = "BDCABA";
	char z[20];
	int result= LCS(x, y,z);
	cout << "Longest common subsequence = "<<z;
	cout << "\nLongest common subsequence length = " <<result ;
	string x2 = "ABBACQ";
	string y2 = "XAYZMBNNALQCTRQ";
	char z2[20];
	int result2 = LCS(x2, y2, z2);
	cout << "\nLongest common subsequence = " << z2;
	cout << "\nLongest common subsequence length = " << result2;
}