gistfile1.txt

1) Construct L[m+1][n+1] using the steps discussed in previous post.

2) The value L[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0).

2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

int max = L[n][m];
int i = n;
int j = m;

int LCS[max];
int index = max-1;
while(i > 0 && j > 0) {
  if(A[i-1] == B[j-1]) {
      LCS[index] = A[i-1];
      index -= 1; i -= 1; j -= 1;
  } else if(L[i-1][j] > L[i][j-1]) {
      i -= 1;
  } else {
      j -= 1;
  }            
}

for(int i=0; i<max; i++) {
  printf("%d ", LCS[i]);
}