// breche.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"

#define D(i,j)   td[((i) + 1)*(n + 1) + (j) +1]
#define I(i,j)   ti[((i) + 1)*(n + 1) + (j) +1]
#define T(i,j)   t[((i) + 1)*(n + 1) + (j) +1]
#define Sub(a,b) (a == b ? 0 : 3)
#define INFINI   ((unsigned int)(~0)>>3)


int breche(Mot x, Longueur m, Mot y, Longueur n, int g, int h) {
   int i, j, *t, *td, *ti;

   td = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
   if (td == NULL) error("breche");
   ti = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
   if (ti == NULL) error("breche");
   t = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
   if (t == NULL) error("breche");

   for (i = -1; i <= m + 1; ++i)
      D(i, -1) = I(i, -1) = INFINI;
   T(-1, -1) = 0;
   T(0, -1) = g;
   for (i = 1; i <= m - 1; ++i)
      T(i, -1) = T(i - 1, -1) + h;
   T(-1, 0) = g;
   for (j = 1; j <= n - 1; ++j)
      T(-1, j) = T(-1, j - 1) + h;
   for (j = 0; j <= n - 1; ++j) {
      D(-1, j) = I(-1, j) = INFINI;
      for (i = 0; i <= m - 1; ++i) {
         D(i, j) = MIN(D(i - 1, j) + h, T(i - 1, j) + g);
         I(i, j) = MIN(I(i, j - 1) + h, T(i, j - 1) + g);
         T(i, j) = MIN(T(i - 1, j - 1) + Sub(x[i], y[j]),
                       MIN(D(i, j), I(i, j)));
      }
   }
   return(T(m - 1, n - 1));
}