// les-alignements.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #include "alignement.h" #include "les-alignements.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) void lesAlignements(Mot x, Longueur m, Mot y, Longueur n, int *t) { Alignement z; z = NULL; la(m - 1, n - 1, z, x, y, n, t); } void la(int i, int j, Alignement z, Mot x, Mot y, Longueur n, int *t) { if (i != -1 && j != -1 && T(i, j) == T(i - 1, j - 1) + Sub(x[i], y[j])) { z = ajouterAuDebutAlignement(z, x[i], y[j]); la(i - 1, j - 1, z, x, y, n, t); z = retirerAuDebutAlignement(z); } if (i != -1 && T(i, j) == T(i - 1, j) + Del(x[i])) { z = ajouterAuDebutAlignement(z, x[i], '-'); la(i - 1, j, z, x, y, n, t); z = retirerAuDebutAlignement(z); } if (j != -1 && T(i, j) == T(i, j - 1) + Ins(y[j])) { z = ajouterAuDebutAlignement(z, '-', y[j]); la(i, j - 1, z, x, y, n, t); z = retirerAuDebutAlignement(z); } if (i == -1 && j == -1) ecrireAlignement(z); }