#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX(A,B) (A<B) ? B : A

typedef struct dcsn {
    char common_elem;
    struct dcsn* next_dcsn;
    int length;
} dcsn_t;

dcsn_t*
make_dcsn(void)
{
    dcsn_t *d = (dcsn_t *)malloc( sizeof( dcsn_t ) );
    //d->common_elem = NULL;
    d->next_dcsn = NULL;
    d->length = 0;
    return d;
}

void
traverse_dcsns( dcsn_t *d )
{
    if( d == NULL ) return;
    if( d->common_elem )
    {
        printf("%c", d->common_elem);
    }
    traverse_dcsns( d->next_dcsn );
}

#define STR_MAX 7
dcsn_t *L[STR_MAX+1][STR_MAX+1];

dcsn_t*
find_lcs( char *str1, char *str2, int i, int j )
{
    printf("Operating on %u %u\n", i, j);
    if( i == 0 || j == 0 )
    {
        return NULL;
    }

    //if( L[i][j] != NULL ) return L[i][j];

    dcsn_t *_d;
    if( str1[ i-1 ] == str2[ j-1 ] )
    {
        _d = make_dcsn();
        _d->common_elem = str1[ i-1 ];
        _d->next_dcsn = find_lcs( str1, str2, i-1, j-1 );
        _d->length = 1 + _d->next_dcsn->length;
    }
    else
    {
        dcsn_t* d_a = find_lcs( str1, str2, i-1, j );
        dcsn_t* d_b = find_lcs( str1, str2, i, j-1 );
        if( d_a == NULL || d_b == NULL )
        {
            if( d_a == NULL && d_b == NULL )
            {
                return NULL;
            }
            else if( d_a == NULL )
            {
                _d = d_b;
            }
            else
            {
                _d = d_a;
            }
        }
        else
        {
            //printf("%u vs %u\n", d_a->length, d_b->length);
            if( d_a->length < d_b->length )
            {
                _d = d_b;
            }
            else
            {
                _d = d_a;
            }
        }
    }

    //L[i][j] = _d;
    return _d;
}

int main() {
    char *str1 = "tester";
    char *str2 = "testery";

    //  Initialize memoization
    /*
    int k, l;
    for( k=0; k<STR_MAX; k++ )
    {
        for( l=0; l<STR_MAX; l++ )
        {
            L[k][l] = NULL;
        }
    }
    */
    printf("hi\n");
    //  Compute solution
    dcsn_t *answer_chain;// = make_dcsn();
	//answer_chain = find_lcs( str1, str2, strlen(str1), strlen(str2) );

	//  Output results
	//printf("Longest common subsequence is %u bytes long:\t", answer_chain->length);
	//traverse_dcsns( answer_chain );
	//printf("\n");
	return 0;
}