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