Hirschberg LCS problem

[arupsarkar]

Hi:

I am trying to find out the Least Common Subsequence (LCS) using Hirscgberberg's divide and conquer method. I have attached my code for your reference. My problem is that I not getting any value in my result.

You can look up LCS in wikipedia.

For example if there are 2 strings "ca" and "a" the result should be "a"
similarly, if there is "capital" and "apple" the result should be "apl" and so on.

When I am putting "ca" and "a" I am not getting any response at all in lcs_result string variable.

// Hirschberg.cpp : Defines the entry point for the console application.
//

#include<iostream>
#include<vector>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;

class Hirschberg{

public:
	Hirschberg();
	~Hirschberg();
	string lcs(int i1, int i2, string s1, string s2);
	vector<int> lcs_length(int m, int n, string s1, string s2);
	string reverseString(string s);
	int lcs_lengthMinimum(vector<int> l1, vector<int>l2, int n);

private:
	vector< vector<int> > vI2Matrix;
	string c1;
	string c2;
	string lcs_result;

};

Hirschberg::Hirschberg(){
	cout << "\t\t Initializing Hirschberg...." << endl;
}

Hirschberg::~Hirschberg(){
	cout << "\t\t De initializing Hirschberg objects..." << endl;
}


vector<int> Hirschberg::lcs_length(int m, int n, string s1, string s2)
{
	vector<vector<int>> v2Dlcs_length (2, vector<int>(n+1));

	//Step 1 initialize
	for(int j = 0; j <= n; j++)
	{
		v2Dlcs_length[1][j] = 0;
	}

	//Step 2 calculate v2Dlcs_length[1][j]
	for(int i = 1; i <= m; i++)
	{
		//shift row up
		for(int k = 0; k <=n ; k++)
		{
			v2Dlcs_length[0][k] = v2Dlcs_length[1][k];
		}

		for(int j=1; j<=n; j++)
		{
			if(s1[i-1] == s2[j-1])
			{
				v2Dlcs_length[1][j] = v2Dlcs_length[0][j-1] + 1;
			}else{
				v2Dlcs_length[1][j] = max(v2Dlcs_length[1][j-1],v2Dlcs_length[0][j]);
			}
		}
		
	}


	vector<int> v1Dlcs_length(n+1);
	for(int j = 0 ; j <= n ; j++)
	{
		v1Dlcs_length[j] = v2Dlcs_length[1][j];
	}
	return v1Dlcs_length;


}

string Hirschberg::reverseString(string s)
{
	string s1;
	string::reverse_iterator rit;
	for ( rit=s.rbegin() ; rit < s.rend(); rit++ )
	{
		s1 = s1 + *rit;
	}
	return s1;
}

int Hirschberg::lcs_lengthMinimum(vector<int> l1, vector<int>l2, int n)
{
	int m = 0;
	int k = 0;
	for(int j = 0; j <= n; j++)
	{
		if( m < (l1[j] + l2[n-j]))
		{
			m = l1[j] + l2[n-j];
			k = j;
		}
	}

	return k;
}

string Hirschberg::lcs(int i1, int i2, string s1, string s2)
{


	int i = 0;
	int j = 0;

	//step 1 trivial case
	if(i2 == 0)
	{
		lcs_result = "";
	}else if(i1 == 1)
	{
		for(j = 0; j < i2; j++)
		{
			if(s1[0] == s2[j])
			{
				lcs_result = "" + s1[0];
				break;
			}else{
				lcs_result = "";
			}
		}
	}else //step 2 non trivial, split the string into 2
	{
		i = static_cast<int>(i1/2);
		cout << "i : \t\t\t\t" << i << endl;
		cout << "i2 : \t\t\t\t" << i2 << endl;
		cout << "i1-1 : \t\t\t\t" << i1-1 << endl;
		cout << "s1.substr(0,i) : \t\t" << s1.substr(0,i) << endl;
		cout << "reverseString(s1.substr(i)) : \t" << reverseString(s1.substr(i)) << endl;
		cout << "s2 : \t\t\t\t" << s2 << endl;
		cout << "reverseString(s2) : \t\t" << reverseString(s2) << endl;

		vector<int> l1 = lcs_length(i,i2,s1.substr(0,i),s2);
		vector<int> l2 = lcs_length(i1-i, i2, reverseString(s1.substr(i)),reverseString(s2));
		
		cout << "==========START==============" << endl;
		for(int v1=0;v1<l1.size();v1++)
		{
			cout << l1[v1] << " " ;
		}
		cout << endl;
		for(int v1=0;v1<l2.size();v1++)
		{
			cout << l2[v1] << " " ;
		}
		cout << endl;
		cout << "=============END===========" << endl;
		
		int k = lcs_lengthMinimum(l1, l2, i2);
		
		cout << "k: " << k << endl;

		c1 = lcs(i, k, s1.substr(0,i), s2.substr(0,k));
		c2 = lcs(i1-i,i2-k,s1.substr(i), s2.substr(k));

		cout << "c1 : " << c1 << endl;
		cout << "c2 : " << c2 << endl;
		lcs_result = c1 + c2;
		//cout << "\t\t\tc: " << c << endl;
	}
	

	return lcs_result;
}

int main(int argc, char * argv[])
{
	//cout << "\t\t =================Hirschber Start=======================" << endl;
	Hirschberg hirschberg;

	string s1 = "ca";
	string s2 = "a";
	/*
	vector<int> v1 = hirschberg.lcs_length(s1.length(), s2.length(), s1, s2);
	vector<int>::iterator itr;
	for(itr = v1.begin(); itr!=v1.end(); itr++){
		cout << *itr << "\t";
	}
	cout << endl;
	*/
	string result = hirschberg.lcs(s1.length(), s2.length(), s1, s2);
	cout << "\t\t Result : " <<result << endl;
	//cout << "\t\t =================Hirschber End=======================" << endl;
	return 0;
}

Thanks

[phantomotap]

I don't have time to look at this right now, but I'll say that if you your algorithm works for larger strings you should start checking to make sure your code isn't pruning short strings due to an "off by one" problem.

Soma