// 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); } }