Hirschberg LCS problem

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.

Code:

// 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