/** * @brief longest common subsequence(LCS)  * @author An * @data  2013.8.26                                                                  **/#include 
    
     #include 
     
      using namespace std;enum Direction { Zero, LeftUp, Up, Left };static int m;    // length of the first sequencestatic int n;     // length of the second sequencestatic int **c;  // the length for every subsequencestatic Direction **b;  // record the pathvoid LCS_Length( string x, string y );void Print_LCS( string x, int i, int j );void PrintTable();int main(){	string x = "ABCBDAB";	string y = "BDCABA";	LCS_Length( x, y );	Print_LCS( x, m, n );	cout << endl;	PrintTable();}void LCS_Length( string x, string y ){	// initialize two tables	m = x.length();	n = y.length();	c = new int*[m + 1];	b = new Direction*[m + 1];	for ( int i = 0; i <= m; ++i )	{		c[i] = new int[n + 1];		b[i] = new Direction[n + 1];	}		// zero row and column	for ( int i = 0; i <= m; ++i )	{		c[i][0] = 0;		b[i][0] = Zero;	}	for ( int j = 1; j <= n; ++j )	{		c[0][j] = 0;		b[0][j] = Zero;	}	// calculate the two tables from bottom to top	for ( int i = 1; i <= m; ++i )	{		for ( int j = 1; j <= n; ++j )		{			if ( x[i - 1] == y[j - 1] )			{				c[i][j] = c[i - 1][j - 1] + 1;				b[i][j] = LeftUp;			}			else if ( c[i - 1][j] >= c[i][j - 1] )			{				c[i][j] = c[i - 1][j];				b[i][j] = Up;			}			else			{				c[i][j] = c[i][j - 1];				b[i][j] = Left;			}		} // end for	} //end for} // end LCS_Length()void Print_LCS( string x, int i, int j ){	if ( i == 0 || j == 0 )	{		return;	}	if ( b[i][j] == LeftUp )	{		Print_LCS( x, i - 1, j - 1 );		cout << x[i - 1];	}	else if ( b[i][j] == Up )	{		Print_LCS( x, i - 1, j );	}	else	{		Print_LCS( x, i, j - 1 );	}}void PrintTable(){	for ( int i = 0; i <= m; ++i )	{		for ( int j = 0; j <= n; ++j )		{			cout << c[i][j] << " ";		}		cout << endl;	}	cout << endl;	for ( int i = 0; i <= m; ++i )	{		for ( int j = 0; j <= n; ++j )		{			cout << b[i][j] << " ";		}		cout << endl;	}}