// arbre-c-suffixes.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #include "automate-suff.h" void descLenteC(Etat p, int k, Etat *resp, int *resk, Mot y, Longueur n) { Etat r, q; Etiquette etiquette; int i, j, ell; while (k < n && cibleParUneLettre(p, y[k], y) != NULL) { q = cibleParUneLettre(p, y[k], y); etiquette = etiq(p, q); j = etiquette.position; ell = etiquette.longueur; i = j; do { ++i; ++k; } while (i < j + ell && k < n && y[i] == y[k]); if (i < j + ell) { oterCible(p, etiquette); r = nouvelEtat(); etiquette.position = j; etiquette.longueur = i - j; fixerCible(p, etiquette, r); etiquette.position = i; etiquette.longueur = ell - i + j; fixerCible(r, etiquette, q); *resp = r; *resk = k; return; } p = q; } *resp = p; *resk = k; } Etat descRapide(Etat r, int j, int k, Mot y) { Etat p, q; Etiquette etiquette; int jp, ell; // Calcul de delta(r, y[j..k - 1]) if (j >= k) return(r); else { q = cibleParUneLettre(r, y[j], y); etiquette = etiq(r, q); jp = etiquette.position; ell = etiquette.longueur; if (j + ell <= k) return(descRapide(q, j + ell, k, y)); else { oterCible(r, etiquette); p = nouvelEtat(); etiquette.position = j; etiquette.longueur = k - j; fixerCible(r, etiquette, p); etiquette.position = jp + k - j; etiquette.longueur = ell - k + j; fixerCible(p, etiquette, q); return(p); } } } Automate arbreCSuffixes(Mot y, Longueur n) { Automate M; Etat fourche, q, t; Etiquette etiquette; int i, j, k, ell; M = nouvelAutomate(); ls(initial(M)) = initial(M); fourche = initial(M); k = 0; for (i = 0; i <= n - 1; ++i) { if (k < i) k = i; if (ls(fourche) == NULL) { t = parent(fourche); etiquette = etiq(t, fourche); j = etiquette.position; ell = etiquette.longueur; if (t == initial(M)) --ell; ls(fourche) = descRapide(ls(t), k - ell, k, y); } descLenteC(ls(fourche), k, &fourche, &k, y, n); if (k < n) { q = nouvelEtat(); etiquette.position = k; etiquette.longueur = n - k; fixerCible(fourche, etiquette, q); sortie(q) = i; } else sortie(fourche) = i; } return(M); }