// un-alignement.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #include "alignement.h" #define T(i,j) t[((i) + 1)*(n + 1) + (j) +1] #define Del(a) 1 #define Ins(a) 1 #define Sub(a,b) (a == b ? 0 : 3) Alignement unAlignement(Mot x, Longueur m, Mot y, Longueur n, int *t) { int i, j; Alignement z; z = NULL; i = m - 1; j = n - 1; while (i != -1 && j != -1) if (T(i, j) == T(i - 1, j - 1) + Sub(x[i], y[j])) { z = ajouterAuDebutAlignement(z, x[i], y[j]); --i; --j; } else if (T(i, j) == T(i - 1, j) + Del(x[i])) { z = ajouterAuDebutAlignement(z, x[i], '-'); --i; } else { z = ajouterAuDebutAlignement(z, '-', y[j]); --j; } while (i != -1) { z = ajouterAuDebutAlignement(z, x[i], '-'); --i; } while (j != -1) { z = ajouterAuDebutAlignement(z, '-', y[j]); --j; } return(z); }