public static <T> List<Pair<T, T>> longestCommonSubsequence(final List<T> paramX, final List<T> paramY,
        final IComparator<T> paramCmp) {
        final List<T> x = paramX;
        final List<T> y = paramY;
        final int n = x.size();
        final int m = y.size();
        final int max = n + m;

        if (paramX == null || paramY == null) {
            return new ArrayList<Pair<T, T>>();
        }

        if (paramX.size() == 0 && paramY.size() == 0) {
            return new ArrayList<Pair<T, T>>();
        }

        final int v[] = new int[2 * max + 1];
        final List<List<Pair<T, T>>> common = new ArrayList<List<Pair<T, T>>>(2 * max + 1);
        for (int i = 0; i <= 2 * max; i++) {
            v[i] = 0;
            common.set(i, new ArrayList<Pair<T, T>>());
        }

        for (int i = 0; i <= max; i++) {
            for (int j = -i; j <= i; j += 2) {
                int idxX;
                if (j == -i || j != i && v[max + j - 1] < v[max + j + 1]) {
                    // System.err.printf("Array index: %d\n", max + j + 1);
                    idxX = v[max + j + 1];
                    common.set(max + j, new ArrayList<Pair<T, T>>(common.get(max + j + 1)));
                } else {
                    idxX = v[max + j - 1] + 1;
                    common.set(max + j, new ArrayList<Pair<T, T>>(common.get(max + j - 1)));
                }
                int idxY = idxX - j;
                while (idxX < n && idxY < m && paramCmp.isEqual(x.get(idxX), y.get(idxY))) {
                    common.set(max + j, common.get(max + j)).add(new Pair<T, T>(x.get(idxX), y.get(idxY)));
                    idxX++;
                    idxY++;
                }

                v[max + j] = idxX;
                if (idxX >= n && idxY >= m) {
                    return common.get(max + j);
                }
            }
        }
        throw new IllegalStateException("We should never get to this point!");
    }
public static < T > List < Pair < T , T > > longestCommonSubsequence ( final List < T > paramX , final List < T > paramY , final IComparator < T > paramCmp ) { final List < T > x = paramX ; final List < T > y = paramY ; final int n = x . size ( ) ; final int m = y . size ( ) ; final int max = n + m ; if ( paramX == null || paramY == null ) { return new ArrayList < Pair < T , T > > ( ) ; } if ( paramX . size ( ) == 0 && paramY . size ( ) == 0 ) { return new ArrayList < Pair < T , T > > ( ) ; } final int v [ ] = new int [ 2 * max + 1 ] ; final List < List < Pair < T , T > > > common = new ArrayList < List < Pair < T , T > > > ( 2 * max + 1 ) ; for ( int i = 0 ; i <= 2 * max ; i ++ ) { v [ i ] = 0 ; common . set ( i , new ArrayList < Pair < T , T > > ( ) ) ; } for ( int i = 0 ; i <= max ; i ++ ) { for ( int j = - i ; j <= i ; j += 2 ) { int idxX ; if ( j == - i || j != i && v [ max + j - 1 ] < v [ max + j + 1 ] ) { idxX = v [ max + j + 1 ] ; common . set ( max + j , new ArrayList < Pair < T , T > > ( common . get ( max + j + 1 ) ) ) ; } else { idxX = v [ max + j - 1 ] + 1 ; common . set ( max + j , new ArrayList < Pair < T , T > > ( common . get ( max + j - 1 ) ) ) ; } int idxY = idxX - j ; while ( idxX < n && idxY < m && paramCmp . isEqual ( x . get ( idxX ) , y . get ( idxY ) ) ) { common . set ( max + j , common . get ( max + j ) ) . add ( new Pair < T , T > ( x . get ( idxX ) , y . get ( idxY ) ) ) ; idxX ++ ; idxY ++ ; } v [ max + j ] = idxX ; if ( idxX >= n && idxY >= m ) { return common . get ( max + j ) ; } } } throw new IllegalStateException ( "We should never get to this point!" ) ; }
Longest common subsequence algorithm. cf. E. Myers. An O(ND) difference
algorithm and its variations. Algorithmica, 1(2): 251-266, 1986

@param <T>
type of data
@param paramX
first list
@param paramY
second list
@param paramCmp
function to compare the items in both lists (equality)
@return lcs, the items in the pairs are equal and taken from list x and
list y.