算法导论 ch15 动态规划 最长公共子序列

1. source codes

#include <iostream>
using namespace std;
typedef enum {
	LR = 0,
	UP = 1,
	LEFT = 2
}DIRECTION;
void printLCS(DIRECTION *b, char *X, int i, int j, int n) {
	if (i == 0|| j == 0) {
		return;
	}
	if (b[i * n + j] == LR) {
		printLCS(b, X, i - 1, j - 1, n);
		cout << X[i - 1]<< " ";
	} else {
		if (b[i * n + j] == UP) {
			printLCS(b, X, i - 1, j, n);
		} else {
			printLCS(b, X, i, j - 1, n);
		}
	}
}
/*
 * A: char sequence 
 * B: char sequence
 * la: length of char sequence A
 * lb: length of char sequence B
 */
void longestCommonSequence(char* A, int la, char* B, int lb) {
	int m = la;
	int n = lb;
	int *c = new int[m * n];
	DIRECTION *b = new DIRECTION[m * n];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			c[i * n + j] = 0;
		}
	}
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (A[i - 1] == B[j - 1]) {
				c[i * n + j] = c[(i - 1) * n + (j - 1)] + 1;
				b[i * n + j] = LR;
			} else {
				if (c[(i - 1) * n + j] >= c[i * n + (j - 1)]) {
					c[i * n + j] = c[(i - 1) * n + j];
					b[i * n + j] = UP;
				} else {
					c[i * n + j] = c[i * n + (j - 1)];
					b[i * n + j] = LEFT;
				}
			}
		}
	}
	cout << "matrix c:"<< endl;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cout << c[ i * n + j]<< " ";
		}
		cout << endl;
	}
	cout << endl;
	cout << "matrix b:"<< endl;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (b[i * n + j] == LR) {
				cout << "//";
			} else {
				if (b[i * n + j] == UP) {
					cout << "|";
				} else {
					cout << "-";
				}
			}
			cout << " ";
		}
		cout << endl;
	}
	
	cout << endl;
	cout << "one of LCS is : ";
	printLCS(b, A, m - 1, n - 1, n);
}
int main() {
	char A[] = { 'A', 'B', 'C', 'B', 'D', 'A', 'B' };
	char B[] = { 'B', 'D', 'C', 'A', 'B', 'A' };
	int la = sizeof(A)/sizeof(char);
	int lb = sizeof(B)/sizeof(char);
	longestCommonSequence(A, la + 1, B, lb + 1);
}

2. test result

matrix c:
0 0 0 0 0 0 0 
0 0 0 0 1 1 1 
0 1 1 1 1 2 2 
0 1 1 2 2 2 2 
0 1 1 2 2 3 3 
0 1 2 2 2 3 3 
0 1 2 2 3 3 4 
0 1 2 2 3 4 4 
matrix b:
/ / / / / / / 
/ | | | / - / 
/ / - - | / - 
/ | | / - | | 
/ / | | | / - 
/ | / | | | | 
/ | | | / | / 
/ / | | | / | 
one of LCS is : B C B A