DP: Longest Common Subsequence (LCS)
06 Oct 2011 |
|
dynamic programming
algorithms
google
C/C++
dynamic programming
algorithms
google
C/C++
Given two sequences X = (x1, x2, … , xmi) and Y= (y1, y2, …, yni) we wish to find a maximum-length common subsequence of X and Y.
Given a sequences X = (x1, x2, … , xmi), Z= (z1, z2, …, zk) is a subsequence of X if there exists a strictly increasing sequence i1, i2, … , ik of indices of X such that for all j= 1, 2, … , k, we have xij = zj.
Given two sequences X and Y , we say that a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y .
int** init_matrix(int n, int m, int d) {
int ** A = new int*[n];
for (int i = 0; i < n; i++) {
A[i] = new int[m];
for (int j = 0; j < m; j++) {
A[i][j] = d;
}
}
return A;
}
void delete_matrix(int** A, int n) {
for (int i = 0; i < n; i++) delete[] A[i];
delete[] A;
}
#define UP 1
#define LEFT 2
#define DIAG 3
void get_path(int* a, int** B, int n, int m, int* c, int &k) {
if (n > 0 && m > 0) {
if (B[n][m] == DIAG) {
get_path(a, B, n - 1, m - 1, c, k);
c[k++] = a[n];
} else if (B[n][m] == UP) {
get_path(a, B, n - 1, m, c, k);
} else
get_path(a, B, n, m - 1, c, k);
}
}
void lcs(int* a, int n, int* b, int m, int* c, int &k) {
int** A = init_matrix(n + 1, m + 1, 0);
int** B = init_matrix(n + 1, m + 1, 0);
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m; j++) {
if (a[i] == b[j]) {
A[i][j] = A[i - 1][j - 1] + 1;
B[i][j] = DIAG;
} else {
if (A[i][j - 1] < A[i - 1][j]) {
A[i][j] = A[i - 1][j];
B[i][j] = UP;
} else {
A[i][j] = A[i][j - 1];
B[i][j] = LEFT;
}
}
}
}
get_path(a, B, n, m, c, k);
delete_matrix(A, n + 1);
delete_matrix(B, n + 1);
}