protected LinkedList<Diff> diff_bisect(String text1,String text2,long deadline){
  int text1_length=text1.length();
  int text2_length=text2.length();
  int max_d=(text1_length + text2_length + 1) / 2;
  int v_offset=max_d;
  int v_length=2 * max_d;
  int[] v1=new int[v_length];
  int[] v2=new int[v_length];
  for (int x=0; x < v_length; x++) {
    v1[x]=-1;
    v2[x]=-1;
  }
  v1[v_offset + 1]=0;
  v2[v_offset + 1]=0;
  int delta=text1_length - text2_length;
  boolean front=(delta % 2 != 0);
  int k1start=0;
  int k1end=0;
  int k2start=0;
  int k2end=0;
  for (int d=0; d < max_d; d++) {
    if (System.currentTimeMillis() > deadline) {
      break;
    }
    for (int k1=-d + k1start; k1 <= d - k1end; k1+=2) {
      int k1_offset=v_offset + k1;
      int x1;
      if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
        x1=v1[k1_offset + 1];
      }
 else {
        x1=v1[k1_offset - 1] + 1;
      }
      int y1=x1 - k1;
      while (x1 < text1_length && y1 < text2_length && text1.charAt(x1) == text2.charAt(y1)) {
        x1++;
        y1++;
      }
      v1[k1_offset]=x1;
      if (x1 > text1_length) {
        k1end+=2;
      }
 else       if (y1 > text2_length) {
        k1start+=2;
      }
 else       if (front) {
        int k2_offset=v_offset + delta - k1;
        if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
          int x2=text1_length - v2[k2_offset];
          if (x1 >= x2) {
            return diff_bisectSplit(text1,text2,x1,y1,deadline);
          }
        }
      }
    }
    for (int k2=-d + k2start; k2 <= d - k2end; k2+=2) {
      int k2_offset=v_offset + k2;
      int x2;
      if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
        x2=v2[k2_offset + 1];
      }
 else {
        x2=v2[k2_offset - 1] + 1;
      }
      int y2=x2 - k2;
      while (x2 < text1_length && y2 < text2_length && text1.charAt(text1_length - x2 - 1) == text2.charAt(text2_length - y2 - 1)) {
        x2++;
        y2++;
      }
      v2[k2_offset]=x2;
      if (x2 > text1_length) {
        k2end+=2;
      }
 else       if (y2 > text2_length) {
        k2start+=2;
      }
 else       if (!front) {
        int k1_offset=v_offset + delta - k2;
        if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
          int x1=v1[k1_offset];
          int y1=v_offset + x1 - k1_offset;
          x2=text1_length - x2;
          if (x1 >= x2) {
            return diff_bisectSplit(text1,text2,x1,y1,deadline);
          }
        }
      }
    }
  }
  LinkedList<Diff> diffs=new LinkedList<Diff>();
  diffs.add(new Diff(Operation.DELETE,text1));
  diffs.add(new Diff(Operation.INSERT,text2));
  return diffs;
}

protected LinkedList < Diff > diff_bisect ( String text1 , String text2 , long deadline ) { int text1_length = text1 . length ( ) ; int text2_length = text2 . length ( ) ; int max_d = ( text1_length + text2_length + 1 ) / 2 ; int v_offset = max_d ; int v_length = 2 * max_d ; int [ ] v1 = new int [ v_length ] ; int [ ] v2 = new int [ v_length ] ; for ( int x = 0 ; x < v_length ; x ++ ) { v1 [ x ] = - 1 ; v2 [ x ] = - 1 ; } v1 [ v_offset + 1 ] = 0 ; v2 [ v_offset + 1 ] = 0 ; int delta = text1_length - text2_length ; boolean front = ( delta % 2 != 0 ) ; int k1start = 0 ; int k1end = 0 ; int k2start = 0 ; int k2end = 0 ; for ( int d = 0 ; d < max_d ; d ++ ) { if ( System . currentTimeMillis ( ) > deadline ) { break ; } for ( int k1 = - d + k1start ; k1 <= d - k1end ; k1 += 2 ) { int k1_offset = v_offset + k1 ; int x1 ; if ( k1 == - d || ( k1 != d && v1 [ k1_offset - 1 ] < v1 [ k1_offset + 1 ] ) ) { x1 = v1 [ k1_offset + 1 ] ; } else { x1 = v1 [ k1_offset - 1 ] + 1 ; } int y1 = x1 - k1 ; while ( x1 < text1_length && y1 < text2_length && text1 . charAt ( x1 ) == text2 . charAt ( y1 ) ) { x1 ++ ; y1 ++ ; } v1 [ k1_offset ] = x1 ; if ( x1 > text1_length ) { k1end += 2 ; } else if ( y1 > text2_length ) { k1start += 2 ; } else if ( front ) { int k2_offset = v_offset + delta - k1 ; if ( k2_offset >= 0 && k2_offset < v_length && v2 [ k2_offset ] != - 1 ) { int x2 = text1_length - v2 [ k2_offset ] ; if ( x1 >= x2 ) { return diff_bisectSplit ( text1 , text2 , x1 , y1 , deadline ) ; } } } } for ( int k2 = - d + k2start ; k2 <= d - k2end ; k2 += 2 ) { int k2_offset = v_offset + k2 ; int x2 ; if ( k2 == - d || ( k2 != d && v2 [ k2_offset - 1 ] < v2 [ k2_offset + 1 ] ) ) { x2 = v2 [ k2_offset + 1 ] ; } else { x2 = v2 [ k2_offset - 1 ] + 1 ; } int y2 = x2 - k2 ; while ( x2 < text1_length && y2 < text2_length && text1 . charAt ( text1_length - x2 - 1 ) == text2 . charAt ( text2_length - y2 - 1 ) ) { x2 ++ ; y2 ++ ; } v2 [ k2_offset ] = x2 ; if ( x2 > text1_length ) { k2end += 2 ; } else if ( y2 > text2_length ) { k2start += 2 ; } else if ( ! front ) { int k1_offset = v_offset + delta - k2 ; if ( k1_offset >= 0 && k1_offset < v_length && v1 [ k1_offset ] != - 1 ) { int x1 = v1 [ k1_offset ] ; int y1 = v_offset + x1 - k1_offset ; x2 = text1_length - x2 ; if ( x1 >= x2 ) { return diff_bisectSplit ( text1 , text2 , x1 , y1 , deadline ) ; } } } } } LinkedList < Diff > diffs = new LinkedList < Diff > ( ) ; diffs . add ( new Diff ( Operation . DELETE , text1 ) ) ; diffs . add ( new Diff ( Operation . INSERT , text2 ) ) ; return diffs ; }
find the ' middle snake ' of a diff , split the problem in two and return the recursively constructed diff . see myers 1986 paper : an o ( nd ) difference algorithm and its variations .
