// aa.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #include "automate-align.h" #define E(i,j) e[((i) + 1)*(n + 1) + (j) +1] #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 aa(int i, int j, Etat *e, int *t, Mot x, Mot y, Longueur n) { PaireAlignee paireAlignee; if (i != -1 && j != -1 && T(i, j) == T(i - 1, j - 1) + Sub(x[i], y[j])) { if (E(i - 1, j - 1) == NULL) { E(i - 1, j - 1) = nouvelEtat(); aa(i - 1, j - 1, e, t, x, y, n); } paireAlignee.haut = x[i]; paireAlignee.bas = y[j]; fixerCible(E(i - 1, j - 1), paireAlignee, E(i, j)); } if (i != -1 && T(i, j) == T(i - 1, j) + Del(x[i])) { if (E(i - 1, j) == NULL) { E(i - 1, j) = nouvelEtat(); aa(i - 1, j, e, t, x, y, n); } paireAlignee.haut = x[i]; paireAlignee.bas = '-'; fixerCible(E(i - 1, j), paireAlignee, E(i, j)); } if (j != -1 && T(i, j) == T(i, j - 1) + Ins(y[j])) { if (E(i, j - 1) == NULL) { E(i, j - 1) = nouvelEtat(); aa(i, j - 1, e, t, x, y, n); } paireAlignee.haut = '-'; paireAlignee.bas = y[j]; fixerCible(E(i, j - 1), paireAlignee, E(i, j)); } }