// calcul-generique.c

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

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

#define T(i,j)   t[((i) + 1)*(n + 1) + (j) +1]
#define Del(a)   1
#define Ins(a)   1
#define Sub(a,b) (a == b ? 0 : 3)


int calculGenerique(Mot x, Longueur m, Mot y, Longueur n) {
   int i, j, *t;

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

   T(-1, -1) = 0;
   for (i = 0; i <= m - 1; ++i)
      T(i, -1) = T(i - 1, -1) + Del(x[i]);
   for (j = 0; j <= n - 1; ++j) {
      T(-1, j) = T(-1, j - 1) + Ins(y[j]);
      for (i = 0; i <= m - 1; ++i)
         T(i, j) = MIN(MIN(T(i - 1, j - 1) + Sub(x[i], y[j]),
                           T(i - 1, j) + Del(x[i])),
                       T(i, j - 1) + Ins(y[j]));
   }
   return(T(m - 1, n - 1));
}