/*
一個給定序列的子序列中刪除若干元素后得到的序列。
確切地說：
若給定序列X={x1,x2,...,xm}，則另一序列Z={z1,z2,...,zk}，是X的子序列
是指存在一個嚴格遞增的下標序列{i1,i2,...,ik}使得對于所有j=1,2,...,k有:
zj = xij。例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應的遞增
下標序列為{2,3,5,7}
給定兩個序列X和Y,當另一序列Z即是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列
最長公共子序列問題是：
給定兩個序列X={x1,x2,...,xm},Y = {y1,y2,...,yn}找出X和Y的一個最長公共子序列
*/

/*
最長公共子序列問題滿足最有子結構性質
設序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}的一個最長公共子序列為Z={z1,z2,...,zk}則
（1）若xm = yn，則zk = xm = yn，且Zk-1是Xm-1和Yn-1的最長公共子序列
（2）若xm != yn，且zk != xm,則Z是Xm-1和Y的最長公共子序列
（3）若xm != yn且zk!= yn則Z是X和Yn-1的最長公共子序列。
*/
/*
子問題的遞歸結構：
要找出X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最長公共子序列，可按以下方式遞歸地進行：
（1）當xm = yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)
（2）當xm != yn時，必須解決兩個子問題，即找出Xm-1和Y的一個最長公共子序列以及
X和Yn-1的一個最長公共子序列，這兩個中的較長的為結果
用c[i][j]表示Xi和Yj的最長公共子序列。Xi={x1,x2,...,xi},Yj={y1,y2,...,yj}
其中Xi = { x1,x2,...,xi},Yj = {y1,y2,...,yj}
當i = 0或j = 0時，空序列是Xi和Yj的最長公共子序列。故此時c[i][j] = 0。其他
情況下，由最優子結構性質可建立遞歸關系如下：
c[i][j] = 0;//i == 0,j == 0
        = c[i-1][j-1] + 1;//i,j>0,xi = yj
		= max{x[i][j-1],c[i-1][j]}//i,j>0,xi != yj
*/

/*
計算最優值：
直接利用遞歸式容易寫出一個c[i][j]的遞歸算法，但是其計算時間是隨著輸入長度
指數增長的。由于在所考慮的子問題空間中，總有O(mn)個不同的子問題，因此動態規劃
算法自底向上計算最優值能提高算法的效率。
計算最長公共子序列長度的動態規劃算法LCSLength以序列X={x1,x2,...,xm}
和Y = {y1,y2,...,yn}作為輸入，輸出兩個數組c和b。其中c[i][j]中存儲
Xi和Yj的最長公共子序列的長度，b[i][j]記錄c[i][j]的值是由哪一個子問題解得的，
這在構造最長公共子序列時要用到。問題的最優值，即X和Y的最長公共子序列的長度記錄
于c[m][n]中。
*/

void LCSLength( int m, int n, char *x, char *y, int **c, char **b )
{
	int i,j;
	for( i = 1; i <= m; ++i )
	{
		c[i][0] = 0;
	}
	
	for( i = 1; i <= n; ++i )
	{
		c[0][i] = 0;
	}

	for( i = 1; i <= m; ++i )
	{
		for( j = 1; j <= n; ++j )
		{
			if ( x[i] == y[j] )
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = '$';
			}
			else if ( c[i-1][j] >= c[i][j-1] )
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 'u';
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = 'l';
			}
		}
	}
}

/*
構造最長公共子序列：
首先從b[m][n]開始，當在b[i][j]中遇到'$'時，表示Xi和Yj的最長公共子序列是Xi-1和Yj-1
的最長公共子序列在末尾加上xi所得到的序列。當在b[i][j]中遇到'u'時表示Xi和Yj的最長公共子序列
與Xi-1和Yj的最長公共子序列相同。當遇到'l'時，表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長
公共子序列相同。
*/
/*
下面的算法LCS實現根據b的內容打印出Xi和Yj的最長公共子序列
*/

void LCS( int i, int j, char *x, char **b )
{
	if ( i ==0 || j ==0 )
	{
		return;
	}

	if ( b[i][j] = '$' )
	{
		LCS( i - 1, j - 1, x, b );
		cout<<x[i]<<endl;
	}
	else if ( b[i][j] == 'u' )
	{
		LCS( i - 1, j, x, b );
	}
	else
	{
		LCS( i, j - 1, x, b );
	}
}

/*
算法的改進：
按照一般算法策略設計的算法，往往在時間和空間的需求上有有較大的改進余地。
（1）在算法LCSLength和LCS中，可以進一步將b省去。
事實上，數組元素的值僅有c[i-1][j-1],c[i-1][j],c[i][j-1]這三個數組元素的值所
確定。對于給定的數組元素c[i][j]，我們可以不借助于數組b僅借助于c本身在O(1)時間
內確定c[i][j]的值是由哪一個確定的。因此可以不用b，而節省o(mn)的空間。
（2）如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減小。事實上
在計算c[i][j]時，只用到數組c的第i行和第i-1行。因此，用兩行的數組空間就可以計算出
最長公共子序列的長度。進一步的分析還可以將空間需求減到O(min{m,n})。
*/

int main()
{
	return 0;
}