Hirschberg LCS problem

This is a discussion on Hirschberg LCS problem within the C++ Programming forums, part of the General Programming Boards category; Hi: I am trying to find out the Least Common Subsequence (LCS) using Hirscgberberg's divide and conquer method. I have ...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    14

    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

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,176
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sleep() function problem or logic problem?
    By FernandoBasso in forum C Programming
    Replies: 7
    Last Post: 11-16-2011, 04:50 PM
  2. strcmp problem, whats the problem, i cant figure it out!
    By AvaGodess in forum C Programming
    Replies: 14
    Last Post: 10-18-2008, 06:45 PM
  3. Replies: 4
    Last Post: 10-16-2008, 07:30 PM
  4. syntax linked list problem & struct problem
    By beely in forum C Programming
    Replies: 5
    Last Post: 11-11-2002, 08:14 AM
  5. Texture Problem(I got the NeHe tut working, but I have a problem)
    By SyntaxBubble in forum Game Programming
    Replies: 2
    Last Post: 12-02-2001, 09:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21