// Path: lcs-algorithms/src/main/java/com/fillumina/lcs/algorithm/myers/BidirectionalVector.java
// public class BidirectionalVector {
// 
//     private final int[] array;
//     private final int zero;
// 
//     /**
//      * @param size specify the positive size (the total size will be
//      *             {@code size * 2 + 1}.
//      */
//     public BidirectionalVector(int size) {
//         this(size, 0);
//     }
// 
//     /**
//      * @param size specify the positive size (the total size will be
//      *             {@code size * 2 + 1}.
//      * @param offset is always subtracted to the given index
//      */
//     public BidirectionalVector(int size, int offset) {
//         int length = size + Math.abs(offset);
//         this.array = new int[(length << 1) + 1];
//         this.zero = length - offset;
//     }
// 
//     /** Clone  constructor. */
//     private BidirectionalVector(int zero, int[] array) {
//         this.zero = zero;
//         this.array = array;
//     }
// 
//     public int get(int x) {
//         return array[zero + x];
//     }
// 
//     public void set(int x, int value) {
//         array[zero + x] = value;
//     }
// 
//     @Override
//     public String toString() {
//         return "" + zero + ":" + Arrays.toString(array);
//     }
// 
//     /** Same as {@link Object#clone()} but without throwing anything. */
//     public BidirectionalVector copy() {
//         int [] cloned = new int[array.length];
//         System.arraycopy(array, 0, cloned, 0, array.length);
//         return new BidirectionalVector(zero, cloned);
//     }
// 
// }


import com.fillumina.lcs.algorithm.myers.BidirectionalVector;
import java.util.ArrayList;
import java.util.List;
package com.fillumina.lcs.algorithm.myers.linearspace;


/**
 * Myers algorithm that uses forward and backward snakes. It is not designed
 * to be fast but to be easy to understand and close to the description
 * given by Myers on his paper.
 *
 * @see <a href='www.xmailserver.org/diff2.pdf'>
 *  An O(ND) Difference Algorithm and Its Variations (PDF)
 * </a>
 *
 * @author Francesco Illuminati
 */
class LinearSpaceMyersLcsSolver<T> {

    private final T[] a;
    private final T[] b;

    public LinearSpaceMyersLcsSolver(T[] a, T[] b) {
        this.a = a;
        this.b = b;
    }

    List<T> calculateLcs() {
        Snake snakes = new Section(0, 0, a.length, b.length).lcs();
        return extractLcs(snakes);
    }

    /** @return the common subsequence elements. */
    private List<T> extractLcs(Snake snakes) {
        List<T> list = new ArrayList<>();
        for (Snake snake : snakes) {
            for (int index : snake.getDiagonal()) {
                list.add(a[index]);
            }
        }
        return list;
    }

    class Section extends Rectangle {

        Section(int xStart, int yStart, int xEnd, int yEnd) {
            super(xStart, yStart, xEnd, yEnd);
        }

        /**
         * Executes the LCS algorithm over this section. Remember that the
         * returned snake is actually an iterable of snakes.
         */
        <T> Snake lcs() {
            if (isImproper()) {
                // has zero size in at least one of its dimensions
                return createNullSnake();
            }

            Snake snake = findMiddleSnake();
            if (hasSameDimentionOf(snake)) {
                // the returned snake has the size of the entire section
                return snake;
            }

            // recurse the algorithm on the sections before and after
            // the returned snake
            Snake before = getSectionBefore(snake).lcs();
            Snake after = getSectionAfter(snake).lcs();

            // chain the snakes containing the solution together
            return Snake.chain(before, snake, after);
        }

        /** Searches for a snake in the section. */
        <T> Snake findMiddleSnake() {
            final int max = (int) Math.ceil((m + n) / 2.0) + 1;
            final int delta = n - m;
            final boolean evenDelta = delta % 2 == 0;

// Path: lcs-algorithms/src/main/java/com/fillumina/lcs/algorithm/myers/BidirectionalVector.java
// public class BidirectionalVector {
// 
//     private final int[] array;
//     private final int zero;
// 
//     /**
//      * @param size specify the positive size (the total size will be
//      *             {@code size * 2 + 1}.
//      */
//     public BidirectionalVector(int size) {
//         this(size, 0);
//     }
// 
//     /**
//      * @param size specify the positive size (the total size will be
//      *             {@code size * 2 + 1}.
//      * @param offset is always subtracted to the given index
//      */
//     public BidirectionalVector(int size, int offset) {
//         int length = size + Math.abs(offset);
//         this.array = new int[(length << 1) + 1];
//         this.zero = length - offset;
//     }
// 
//     /** Clone  constructor. */
//     private BidirectionalVector(int zero, int[] array) {
//         this.zero = zero;
//         this.array = array;
//     }
// 
//     public int get(int x) {
//         return array[zero + x];
//     }
// 
//     public void set(int x, int value) {
//         array[zero + x] = value;
//     }
// 
//     @Override
//     public String toString() {
//         return "" + zero + ":" + Arrays.toString(array);
//     }
// 
//     /** Same as {@link Object#clone()} but without throwing anything. */
//     public BidirectionalVector copy() {
//         int [] cloned = new int[array.length];
//         System.arraycopy(array, 0, cloned, 0, array.length);
//         return new BidirectionalVector(zero, cloned);
//     }
// 
// }


// Path: lcs-algorithms/src/main/java/com/fillumina/lcs/algorithm/myers/linearspace/LinearSpaceMyersLcsSolver.java
import com.fillumina.lcs.algorithm.myers.BidirectionalVector;
import java.util.ArrayList;
import java.util.List;

package com.fillumina.lcs.algorithm.myers.linearspace;


/**
 * Myers algorithm that uses forward and backward snakes. It is not designed
 * to be fast but to be easy to understand and close to the description
 * given by Myers on his paper.
 *
 * @see <a href='www.xmailserver.org/diff2.pdf'>
 *  An O(ND) Difference Algorithm and Its Variations (PDF)
 * </a>
 *
 * @author Francesco Illuminati
 */
class LinearSpaceMyersLcsSolver<T> {

    private final T[] a;
    private final T[] b;

    public LinearSpaceMyersLcsSolver(T[] a, T[] b) {
        this.a = a;
        this.b = b;
    }

    List<T> calculateLcs() {
        Snake snakes = new Section(0, 0, a.length, b.length).lcs();
        return extractLcs(snakes);
    }

    /** @return the common subsequence elements. */
    private List<T> extractLcs(Snake snakes) {
        List<T> list = new ArrayList<>();
        for (Snake snake : snakes) {
            for (int index : snake.getDiagonal()) {
                list.add(a[index]);
            }
        }
        return list;
    }

    class Section extends Rectangle {

        Section(int xStart, int yStart, int xEnd, int yEnd) {
            super(xStart, yStart, xEnd, yEnd);
        }

        /**
         * Executes the LCS algorithm over this section. Remember that the
         * returned snake is actually an iterable of snakes.
         */
        <T> Snake lcs() {
            if (isImproper()) {
                // has zero size in at least one of its dimensions
                return createNullSnake();
            }

            Snake snake = findMiddleSnake();
            if (hasSameDimentionOf(snake)) {
                // the returned snake has the size of the entire section
                return snake;
            }

            // recurse the algorithm on the sections before and after
            // the returned snake
            Snake before = getSectionBefore(snake).lcs();
            Snake after = getSectionAfter(snake).lcs();

            // chain the snakes containing the solution together
            return Snake.chain(before, snake, after);
        }

        /** Searches for a snake in the section. */
        <T> Snake findMiddleSnake() {
            final int max = (int) Math.ceil((m + n) / 2.0) + 1;
            final int delta = n - m;
            final boolean evenDelta = delta % 2 == 0;

            final BidirectionalVector vf = new BidirectionalVector(max);