1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Hirschberg LCS problem

Discussion in 'C++' started by arupsarkar, May 14, 2012.

  1. arupsarkar

    arupsarkar New Member

    Joined:
    Aug 17, 2010
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    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
     

Share This Page