// smc.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include <string.h> #include "chl.h" #include "sous-mot.h" #include "smc-colonne.h" #define C1(i) c1[(i) + 1] #define C2(i) c2[(i) + 1] #define P1(i) p1[(i) + 1] #define P2(i) p2[(i) + 1] int estDansAlpha(Lettre a, Mot w, Longueur ell) { Mot u; u = strchr(w, a); return( u != NULL && u - w < ell); } SousMot smc(Mot x, Longueur m, Mot y, Longueur n) { int i, j, k, *c, *c1, *c2, *p, *p1, *p2; SousMot u, v; c2 = (int *)malloc((m + 2)*sizeof(int)); if (c2 == NULL) error("smc"); p1 = (int *)malloc((m + 2)*sizeof(int)); if (p1 == NULL) error("smc"); p2 = (int *)malloc((m + 2)*sizeof(int)); if (p2 == NULL) error("smc"); if (m == 1 && estDansAlpha(x[0], y, n)) return(creerSousMot(x[0])); else if (n == 1 && estDansAlpha(y[0], x, m)) return(creerSousMot(y[0])); else if (m <= 1 || n <= 1) return(NULL); c1 = smcColonne(x, m, y, n/2); for (i = -1; i <= m - 1; ++i) P1(i) = i + 1; for (j = n/2; j <= n - 1; ++j) { C2(-1) = 0; P2(-1) = 0; for (i = 0; i <= m - 1; ++i) if (x[i] == y[j]) { C2(i) = C1(i - 1) + 1; P2(i) = P1(i - 1); } else if (C1(i) > C2(i - 1)) { C2(i) = C1(i); P2(i) = P1(i); } else { C2(i) = C2(i - 1); P2(i) = P2(i - 1); } c = c1; c1 = c2; c2 = c; p = p1; p1 = p2; p2 = p; } k = P1(m - 1); u = smc(x, k, y, n/2); v = smc(x + k, m - k, y + n/2, n - n/2); return(concatenerSousMot(u, v)); }