lcs.cpp

动态规划解决LCS

#include <iostream.h>

const int m = 7, n = 6;
char x[m+1] = {' ', 'A', 'B', 'C', 'B', 'D', 'A', 'B'},
	y[n+1] = {' ', 'B', 'D', 'C', 'A', 'B', 'A'};
int c[m+1][n+1];
char b[m+1][n+1];

void LCSLength(){
	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] = '|';
				}
				else{
					c[i][j] = c[i][j-1];
					b[i][j] = '-';
				}
		}
}

void LCS(int i, int j){
	if (i == 0 || j == 0) return;
	if (b[i][j] == '\\'){
		LCS(i-1, j-1);
		cout << x[i] << ", ";
	}
	else
		if (b[i][j] == '|')
			LCS(i-1, j);
		else
			LCS(i, j-1);
}

void main(){
	cout << "设所给的 2 个序列为 X = {A, B, C, B, D, A, B}，Y = {B, D, C, A, B, A}。" << endl
		<< "由算法 LCSLength 和 LCS 计算出的结果如下图所示：" << endl;
	LCSLength();
	for (int i = 0; i <= m; i++){
		for (int j = 0; j <= n; j++)
			cout << "  " << c[i][j] << b[i][j] << "  ";
		cout << endl;
	}
	cout << "* 构造最长公共子序列 LCS 为: <";
	LCS(m, n);
	cout << "\b\b>" << endl;
}