// l-diff-elag.c

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

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

#define C1(i)   c1[(i) + 1]
#define C2(i)   c2[(i) + 1]


void lDiffElag(Mot x, Longueur m, Mot y, Longueur n, int k) {
   int i, j, p, *c, *c1, *c2;

   c1 = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
   if (c1 == NULL) error("lDiffElag");
   c2 = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
   if (c2 == NULL) error("lDiffElag");

   for (i = -1; i <= m - 1; ++i)
      C1(i) = i + 1;
   p = k;
   for (j = 0; j <= n - 1; ++j) {
      C2(-1) = 0;
      for (i = 0; i <= p; ++i)
         if (x[i] == y[j])
            C2(i) = C1(i - 1);
         else
            C2(i) = MIN(MIN(C1(i - 1), C2(i - 1)), C1(i)) + 1;
      c = c1;
      c1 = c2;
      c2 = c;
      while (C1(p) > k)
         --p;
      signalerSi(p == m - 1);
      ++p;
      p = MIN(p, m - 1);
   }
}