#include <stdio.h>

#define d(i,j) dd[(i) * (m+2) + (j) ]
#define min(x,y) ((x) < (y) ? (x) : (y))
#define min3(a,b,c) ((a)< (b) ? min((a),(c)) : min((b),(c)))
#define min4(a,b,c,d) ((a)< (b) ? min3((a),(c),(d)) : min3((b),(c),(d)))

int dprint(int* dd, int n,int m){
 int i,j;
 for (i=0; i < n+2;i++){
    for (j=0;j < m+2; j++){
        printf("%02d ",d(i,j));
    }
    printf("\n");
 }
 printf("\n");
 return 0;
}

int dldist2(char *s, char* t, int n, int m) {
    int *dd;
    int i, j, cost, i1,j1,DB;
    int INFINITY = n + m;
    static int DA[256 * sizeof(int)];

    memset(DA, 0, sizeof(DA));

    if (!(dd = (int*) malloc((n+2)*(m+2)*sizeof(int)))) {
      printf("malloc error\n");
      return -1;
    }

    d(0,0) = INFINITY;
    for(i = 0; i < n+1; i++) {
      d(i+1,1) = i ;
      d(i+1,0) = INFINITY;
    }
    for(j = 0; j<m+1; j++) {
      d(1,j+1) = j ;
      d(0,j+1) = INFINITY;
    }      
//    dprint(dd,n,m);

    for(i = 1; i< n+1; i++) {
      DB = 0;
      for(j = 1; j< m+1; j++) {
        i1 = DA[t[j-1]];
        j1 = DB;
        cost = ((s[i-1]==t[j-1])?0:1);
        if(cost==0) DB = j;
        d(i+1,j+1) =
          min4(d(i,j)+cost,
              d(i+1,j) + 1,
              d(i,j+1)+1, 
              d(i1,j1) + (i-i1-1) + 1 + (j-j1-1));
      }
      DA[s[i-1]] = i;
//      dprint(dd,n,m);
    }
    cost = d(n+1,m+1);
    free(dd);
    return cost;
}

int main(void) {
	int cost;
	int msize;
	int nsize;
	
	msize = 8;
	nsize = 8;
	cost = dldist2("ABNANA", "BANANA", nsize, msize);
	printf("%.3f\n", cost / (float)(nsize * msize));
	msize = 16;
	nsize = 16;
	cost = dldist2("ABNANA", "BANANA", nsize, msize);
	printf("%.3f\n", cost / (float)(nsize * msize));

	return 0;
}