/*
class Main {
  // Space optimized function to find the length of the longest common
  // subsequence of substring `X[0…m-1]` and `Y[0…n-1]`
  public static int LCSLength(String X, String Y) {
    int m = X.length(), n = Y.length();

    // allocate storage for one-dimensional arrays, `curr` and `prev`
    int[] curr = new int[n + 1];
    int[] prev = new int[n + 1];

    // fill the lookup table in a bottom-up manner
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i > 0 && j > 0) {
          // if the current character of `X` and `Y` matches
          if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            curr[j] = prev[j - 1] + 1;
          } else {
            curr[j] = Integer.max(prev[j], curr[j - 1]);
          }
        }
      }

      // replace contents of the previous array with the current array
      int[] temp = curr;
      curr = prev;
      prev = temp;
      //System.arraycopy(curr, 0, prev, 0, n + 1);
    }

    // LCS will be the last entry in the lookup table
    return curr[n];
  }

  public static void main(String[] args) {
    String X = "XMJYAUZ", Y = "MZJAWXU";

    System.out.println("The length of the LCS is " + LCSLength(X, Y));
  }
}
*/



/*
class Main {
  // Space optimized function to find the length of the longest
  // common subsequence of substring `X[0…m-1]` and `Y[0…n-1]`
  public static int LCSLength(String X, String Y) {
    int m = X.length(), n = Y.length();
 
    // allocate storage for one-dimensional array `curr`
    int[] curr = new int[n + 1];
    int prev;
 
    // fill the lookup table in a bottom-up manner
    for (int i = 0; i <= m; i++) {
      prev = curr[0];
      for (int j = 0; j <= n; j++) {
        int backup = curr[j];
        if (i == 0 || j == 0) {
          curr[j] = 0;
        } else {
          // if the current character of `X` and `Y` matches
          if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            curr[j] = prev + 1;
          } else {
            curr[j] = Integer.max(curr[j], curr[j - 1]);
          }
        }
        prev = backup;
      }
    }
 
    // LCS will be the last entry in the lookup table
    return curr[n];
  }
 
  public static void main(String[] args) {
    String X = "XMJYAUZ", Y = "MZJAWXU";
 
    // pass smaller string as a second argument to `LCSLength()`
    if (X.length() > Y.length()) {
      System.out.println("The length of the LCS is " + LCSLength(X, Y));
    } else {
      System.out.println("The length of the LCS is " + LCSLength(Y, X));
    }
  }
}
*/








class Main {
  // Space optimized function to find the length of the longest
  // common subsequence of substring 'X[0…m-1]' and 'Y[0…n-1]'
  String x, y;
  int m, n;
  int[] lenLCS;
  int[] locLCS;
  int[] f;
  int[] b;

  Main(String x, String y) {
    this.x = x;
    this.y = y;
    m = x.length();
    n = y.length();
    System.out.println("m: " + m + "   n: " + n);
    lenLCS = new int[m+1];
    locLCS = new int[m+1];
    f = new int[n+1];
    b = new int[n+1];

    int max = LCSpart(0, m + 1, 0, n);
    System.out.println("max: " + max);
    for(int i = 0; i <= m; i++) {
      System.out.println(lenLCS[i] + " " + locLCS[i] + " "
                         + (i < m ? x.charAt(i) : ' ')
                         + " " + (locLCS[i] < n ? y.charAt(locLCS[i]) : ' '));
    }
    for(int i = 0; i < m; i++) {
      if(lenLCS[i] < lenLCS[i + 1]) {
        System.out.print("" + x.charAt(i));
      }
    }
    System.out.println();
    for(int i = 0; i < m; i++) {
      if(lenLCS[i] < lenLCS[i + 1]) {
        System.out.print("" + y.charAt(locLCS[i+1]-1));
      }
    }
    System.out.println();
    System.out.println("Match indices");
    for(int i = 0; i < m; i++) {
      if(lenLCS[i] < lenLCS[i + 1]) {
        System.out.println(i + " " + (locLCS[i+1]-1));
      }
    }
    System.out.println("delete | add");
    int left1 = 0;
    int right1 = 0;
    for(int i = 0; i <= m; i++) {
      //System.out.println(lenLCS[i] + " " + lenLCS[i + 1]);
      if(i == m || lenLCS[i] < lenLCS[i + 1]) {
        int left2 = i;
        int right2 = i != m ? locLCS[i+1]-1 : n;
        System.out.println(x.substring(left1, left2) + '|'
                           + y.substring(right1, right2));
        left1 = left2 + 1;
        right1 = right2 + 1;
      }
    }
    System.out.println("left1: " + left1 + "   right1: " + right1);
  }

  /**
   * @param
   */
  int LCSpart(int lom, int him, int lon, int hin) {
    System.out.println(lom + " " + him + " " + lon + " " + hin);
    int midm = (lom + him)/2;
    if(midm == lom) return -1;
    forward(lom, midm, lon, hin); // uses forward array f[]
    backward(midm, him, lon, hin); // uses backward array b[]
    int maxLCS = -1;
    int maxj = 0;
    for(int j = lon; j <= hin; j++) {
      int len = f[j] + b[j];
      if(len > maxLCS) {
        maxLCS = len;
        maxj = j;
      }
    }
    locLCS[midm] = maxj;
    lenLCS[midm] = f[maxj] + lenLCS[lom];
    LCSpart(lom, midm, lon, maxj);
    int r = LCSpart(midm, him, maxj, hin);
    return r < 0 ? maxj : r;
  }

  int forward(int lom, int him, int lon, int hin) {
    int prev;
 
    // fill the lookup table in a bottom-up manner
    for (int i = lom; i <= him; i++) {
      prev = f[lon];
      for (int j = lon; j <= hin; j++) {
        int backup = f[j];
        if (i == lom || j == lon) {
          f[j] = 0; //lenLCS[lom]; /////////////// 
        } else {
          // if the current character of 'X' and 'Y' matches
          if (x.charAt(i - 1) == y.charAt(j - 1)) {
            f[j] = prev + 1;
          } else {
            f[j] = Integer.max(f[j], f[j - 1]);
          }
        }
        prev = backup;
      }
    }
    // LCS will be the last entry in the lookup table
    return f[hin];
  }

  int backward(int lom, int him, int lon, int hin) {
    int prev;
    // fill the lookup table in a bottom-up manner
    for (int i = him; i >= lom; i--) {
      prev = b[hin];
      for (int j = hin; j >= lon; j--) {
        int backup = b[j];
        if (i == him || j == hin) {
          b[j] = 0; // lenLCS[lom]; /////////////// 
        } else {
          // if the current character of 'X' and 'Y' matches
          if (i != m && x.charAt(i) == y.charAt(j)) {
            b[j] = prev + 1; // + lenLCS[lom];
          } else {
            b[j] = Integer.max(b[j], b[j + 1]); // + lenLCS[lom];
          }
        }
        prev = backup;
      }
    }
    // LCS will be the last entry in the lookup table
    return b[lon];
  }

  static int LCSLength(String X, String Y) {
    int m = X.length(), n = Y.length();
 
    // allocate storage for one-dimensional array 'curr'
    int[] curr = new int[n + 1];
    int prev;
 
    // fill the lookup table in a bottom-up manner
    for (int i = 0; i <= m; i++) {
      prev = curr[0];
      for (int j = 0; j <= n; j++) {
        int backup = curr[j];
        if (i == 0 || j == 0) {
          curr[j] = 0;
        } else {
          // if the current character of 'X' and 'Y' matches
          if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            curr[j] = prev + 1;
          } else {
            curr[j] = Integer.max(curr[j], curr[j - 1]);
          }
        }
        prev = backup;
      }
    }
 
    // LCS will be the last entry in the lookup table
    return curr[n];
  }
 
  public static void main(String[] args) {
    String X = args[0], Y = args[1];
 
    System.out.println("The length of the LCS is " + LCSLength(X, Y));
    System.out.println("The length of the LCS is " + LCSLength(Y, X));
    new Main(args[0], args[1]);
  }
}