// l-diff-diag.c

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

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

#define L(q,d)   tl[((q) + 1)*(n + 1) + (d) + m]


void lDiffDiag(Mot x, Longueur m, Mot y, Longueur n, int k) {
   int j, ell, q, *tl;

   tl = (int *)malloc((k + 2)*(n + 2)*sizeof(int));
   if (tl == NULL) error("lDiffDiag");

   for (j = -1; j <= n - m + k + 1; ++j)
      L(-1, j) = -2;
   for (q = 0; q <= k; ++q)
      for (j = -q; j <= n - m + k - q; ++j) {
         ell = MAX(MAX(L(q - 1, j - 1), L(q - 1, j) + 1), L(q - 1, j + 1) + 1);
         ell = MIN(ell, m - 1);
         L(q, j) = ell + llpc(x + ell + 1, y + j + ell + 1);
         signalerSi(L(q, j) == m - 1 || j + L(q, j) == n - 1);
      }
}