#include "Library.h"

template<class T, bool EQ(T,T),bool REVERSE>
void linear_space_lcs_b(const T *a, int alen, const T *b, int blen, int *ll) {
    int *k0 = new int[blen+1];
    int *k1 = new int[blen+1];
    int *tmp;
    int i,j;
    k1[blen] = 0;
    for(i=blen;i>=0;i--) k0[i] = 0;
    for(i=alen-1;i>=0;i--) {
        tmp = k0; k0 = k1; k1 = tmp;
        for(j=blen-1;j>=0;j--) {
            if(EQ(a[REVERSE ? alen-i-1 : i],b[REVERSE ? blen-j-1 : j]))
                k0[j] = k1[j+1] + 1;
            else
                k0[j] = k1[j] > k0[j+1] ? k1[j] : k0[j+1];
        }
            
    }
    for(i=blen;i>=0;i--) ll[i] = k0[i];
    delete k0;
    delete k1;
}

template<class T, bool EQ(T,T)>
Pair<List<T>*,int> linear_space_lcs(const T* a, int alen, const T* b, int blen) {
    Pair<List<T>*,int> ret = { 0, 0 },ret2,ret3;
    int *l1,*l2;
    int i,j,k,max;
    if(alen == 1) {
        for(j=blen-1;j>=0;j--) {
            if(EQ(a[0],b[j])) {
                ret.a = cons<T>(a[0],0);
                ret.b = 1;
                break;
            }
        } 
    } else if(blen != 0) {
        i = alen / 2;
        l1 = new int[blen+1];
        l2 = new int[blen+1];
        linear_space_lcs_b<T,EQ,true>(a,i,b,blen,l1);
        linear_space_lcs_b<T,EQ,false>(a+i,alen-i,b,blen,l2);
        for(k=-1,max=-1,j=blen;j>=0;j--) 
            if(l1[blen-j] + l2[j] > max) { max = l1[blen-j] + l2[j]; k = j; }

        ret2 = linear_space_lcs<T,EQ>(a,i,b,k);
        assert(ret2.b == l1[blen-k]);
        delete l1;

        ret3 = linear_space_lcs<T,EQ>(a+i,alen-i,b+k,blen-k);
        assert(ret3.b == l2[k]);
        delete l2;

        ret.a = concat(ret2.a,ret3.a);
        deepFreeList(ret2.a);
        ret.b = ret2.b + ret3.b;
    }
    return ret;
}