DP: Longest Common Subsequence (LCS)

06 Oct 2011 | By Mihai Roman | Tags 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); 
}

blog comments powered by Disqus