// alignement-local.c

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

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

#define S(i,j)   s[((i) + 1)*(n + 1) + (j) +1]
#define Dels(a)   (-1)
#define Inss(a)   (-1)
#define Subs(a,b) (a == b ? 1 : (-3))


int *alignementLocal(Mot x, Longueur m, Mot y, Longueur n) {
   int i, j, *s;

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

   for (i = -1; i <= m - 1; ++i) S(i, -1) = 0;   // memset(s, 0, (m + 1)*sizeof(int));
   for (j = 0; j <= n - 1; ++j) {
      S(-1, j) = 0;
      for (i = 0; i <= m - 1; ++i)
         S(i, j) = MAX(MAX(0, S(i - 1, j - 1) + Subs(x[i], y[j])),
                       MAX(S(i - 1, j) + Dels(x[i]), S(i, j - 1) + Inss(y[j])));
   }
   return(s);
}