最长公共子序列.cpp

算法分析部分

/*
一个给定序列的子序列中删除若干元素后得到的序列。
确切地说：
若给定序列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;
}