public class LCS {


  public static String longestCommonSubseq( String u, String v ) {
  
    int rows = u.length() + 1;
    int cols = v.length() + 1;
    int[][] length = new int[rows][cols];
    boolean[][] down = new boolean[rows][cols];
    boolean[][] right = new boolean[rows][cols];
    int i, j;
    
    for (i=0; i<rows; i=i+1) {
      for (j=0; j<cols; j=j+1) {
        length[i][j] = undefined;
        down[i][j] = false;
        right[i][j] = false;
      }
    }
    int lgt = memoization_lcs( 0,0, u,v, length, down,right );
    
    String result = "";
    i = 0;
    j = 0;
    while ((i < rows-1) && (j < cols-1)) {
        
      if (down[i][j] && right[i][j]) {
        result = result + u.charAt(i);
        i = i + 1;
        j = j + 1;
      } else if (down[i][j]) {
        i = i + 1;
      } else if (right[i][j]) {
        j = j + 1;
      }
    }
    return result;
  }
  
  public static final int undefined = -1;

  public static int memoization_lcs( int i, int j, String u, String v,
                      int[][] length, boolean[][] down, boolean[][] right ) {
  
    if ( length[i][j] == undefined ) {
    
      if ( (i == u.length()) || (j == v.length()) ) {
      
        length[i][j] = 0;
      
      } else if ( u.charAt(i) == v.charAt(j) ) {
      
        length[i][j] =
          memoization_lcs( i+1,j+1, u,v, length, down,right ) + 1;
        down[i][j] = true;
        right[i][j] = true;
      
      } else {
      
        int d = memoization_lcs( i+1,j, u,v, length, down,right );
        int r = memoization_lcs( i,j+1, u,v, length, down,right );
        
        if (d < r) {
          length[i][j] = r;
          right[i][j] = true;
        } else {
          length[i][j] = d;
          down[i][j] = true;
        }
      
      }
    }
    return length[i][j];
  }

}