LinkedList<Change> bisect(String text1, String text2) {
        // Cache the text lengths to prevent multiple calls.
        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;
        // If the total number of characters is odd, then the front path will
        // collide with the reverse path.
        boolean front = (delta % 2 != 0);
        // Offsets for start and end of k loop.
        // Prevents mapping of space beyond the grid.
        int k1start = 0;
        int k1end = 0;
        int k2start = 0;
        int k2end = 0;
        for (int d = 0; d < max_d; d++) {
            // Bail out if deadline is reached.
            if (options.getClock().millis() > deadline) {
                break;
            }

            // Walk the front path one step.
            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) {
                    // Ran off the right of the graph.
                    k1end += 2;
                } else if (y1 > text2_length) {
                    // Ran off the bottom of the graph.
                    k1start += 2;
                } else if (front) {
                    int k2_offset = v_offset + delta - k1;
                    if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
                        // Mirror x2 onto top-left coordinate system.
                        int x2 = text1_length - v2[k2_offset];
                        if (x1 >= x2) {
                            // Overlap detected.
                            return bisectSplit(text1, text2, x1, y1);
                        }
                    }
                }
            }

            // Walk the reverse path one step.
            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) {
                    // Ran off the left of the graph.
                    k2end += 2;
                } else if (y2 > text2_length) {
                    // Ran off the top of the graph.
                    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;
                        // Mirror x2 onto top-left coordinate system.
                        x2 = text1_length - x2;
                        if (x1 >= x2) {
                            // Overlap detected.
                            return bisectSplit(text1, text2, x1, y1);
                        }
                    }
                }
            }
        }
        // DiffBase took too long and hit the deadline or
        // number of diffs equals number of characters, no commonality at all.
        LinkedList<Change> diffs = new LinkedList<Change>();
        diffs.add(new Change(Operation.DELETE, text1));
        diffs.add(new Change(Operation.INSERT, text2));
        return diffs;
    }
LinkedList < Change > bisect ( String text1 , String text2 ) { 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 ( options . getClock ( ) . millis ( ) > 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 bisectSplit ( text1 , text2 , x1 , y1 ) ; } } } } 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 bisectSplit ( text1 , text2 , x1 , y1 ) ; } } } } } LinkedList < Change > diffs = new LinkedList < Change > ( ) ; diffs . add ( new Change ( Operation . DELETE , text1 ) ) ; diffs . add ( new Change ( 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.

@param text1 Old string to be diffed.
@param text2 New string to be diffed.
@return LinkedList of DiffBase objects.