question: 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 ; }
target:  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.