#include "Library.h"

template<class T, bool EQ(T,T)>
Pair<List<T>*,int> dynamic_lcs(const T *a, int alen, const T *b, int blen) {
    Pair<List<T>*,int> *table = new Pair<List<T>*,int>[(alen+1)*(blen+1)];
    Pair<List<T>*,int> *ent, *ent2, *ent3, ret;
    int i,j;
    for(i=0;i<=blen;i++) {
        table[alen*(blen+1)+i].a = 0;
        table[alen*(blen+1)+i].b = 0;
    }
    for(i=0;i<=alen;i++) {
        table[(blen+1)*i+blen].a = 0;
        table[(blen+1)*i+blen].b = 0;
    }
    for(i=alen-1;i>=0;i--) {
        for(j=blen-1;j>=0;j--) {
            ent = &table[i*(blen+1)+j];
            if(EQ(a[i],b[j])) {
                ent2 = &table[(i+1)*(blen+1)+(j+1)];
                ent->a = cons(a[i],ent2->a);
                ent->b = ent2->b + 1;
            } else {
                ent2 = &table[(i+1)*(blen+1)+(j+0)];
                ent3 = &table[(i+0)*(blen+1)+(j+1)];
                *ent = ent2->b > ent3->b ? *ent2 : *ent3;
            }
        }
    }
    ret = table[0];
    delete table;
    return ret;
}