// l-diff-dyn.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #define R(i,j) r[((i) + 1)*(n + 1) + (j) +1] #define Del(a) 1 #define Ins(a) 1 #define Sub(a,b) (a == b ? 0 : 1) void lDiffDyn(Mot x, Longueur m, Mot y, Longueur n, int k) { int i, j, *r; r = (int *)malloc((m + 2)*(n + 2)*sizeof(int)); if (r == NULL) error("lDiffDyn"); R(-1, -1) = 0; for (i = 0; i <= m - 1; ++i) R(i, -1) = R(i - 1, -1) + Del(x[i]); for (j = 0; j <= n - 1; ++j) { R(-1, j) = 0; for (i = 0; i <= m - 1; ++i) R(i, j) = MIN(MIN(R(i - 1, j - 1) + Sub(x[i], y[j]), R(i - 1, j) + Del(x[i])), R(i, j - 1) + Ins(y[j])); signalerSi(R(m - 1, j) <= k); } }