#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 << "設(shè)所給的 2 個序列為 X = {A, B, C, B, D, A, B}，Y = {B, D, C, A, B, A}。" << endl
		<< "由算法 LCSLength 和 LCS 計算出的結(jié)果如下圖所示：" << 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 << "* 構(gòu)造最長公共子序列 LCS 為: <";
	LCS(m, n);
	cout << "\b\b>" << endl;
}