#include <string.h>

static int  _prefix_distance(char *A, char *B, int lA, int lB);
static int  min(int a, int b, int c);
static void score(int *pD, char *A, char *B, int lA, int lB);

#define D(r,c) pD[(r)*lB1+(c)]

int distance(char *A, char *B)
{
    int *pD, d;

    int lA  = strlen(A);
    int lB  = strlen(B);

    int lA1 = lA+1;
    int lB1 = lB+1;

    pD = (int *) malloc(lA1 * lB1 * sizeof(int));
    if (!pD)
	return -1;
    
    score(pD, A, B, lA, lB);

    d = D(lA,lB);
    free(pD);
    return d;
}


int prefix_distance(char *A, char *B)
{
    int lA  = strlen(A);
    int lB  = strlen(B);

    return lA < lB ? _prefix_distance(A, B, lA, lB) :
	             _prefix_distance(B, A, lB, lA);
}

static int _prefix_distance(char *A, char *B, int lA, int lB)
{
    int *pD, c, d;

    int lA1 = lA+1;
    int lB1 = lB+1;

    pD = (int *) malloc(lA1 * lB1 * sizeof(int));
    if (!pD)
	return -1;
    
    score(pD, A, B, lA, lB);

    d = D(lA, lA);
    for (c=lA+1; c<=lB; c++)
	if (d > D(lA, c))
	    d = D(lA, c);

    free(pD);
    return d;
}


static void score(int *pD, char *A, char *B, int lA, int lB)
{
    int r, c;

    int lB1 = lB+1;

    for (r=0; r<=lA; r++) D(r,0) = r;
    for (c=0; c<=lB; c++) D(0,c) = c;

    for (r=1; r<=lA; r++)
    {
	for (c=1; c<=lB; c++)
	{
	    int u    = D(r-1,c  );
	    int l    = D(r  ,c-1);
	    int ul   = D(r-1,c-1);
	    int cost = A[r-1]==B[c-1] ? 0 : 1;
	    D(r,c)   = min(u+1, l+1, ul+cost);
	}
    }
}

static int min(int a, int b, int c)
{
    int min = a;
    if (min>b) min = b;
    if (min>c) min = c;

    return min;
}