1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
// arbre-suffixes.c
// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.
#include <stdio.h>
#include "chl.h"
#include "automate.h"
void descLente(Etat p, int k, Etat *resp, int *resk, Mot y, Longueur n) {
while (k < n && cible(p, y[k]) != NULL) {
p = cible(p, y[k]);
++k;
}
*resp = p;
*resk = k;
}
Automate arbreSuffixes(Mot y, Longueur n) {
Automate M;
Etat fourche, p, q;
int i, j, k;
M = nouvelAutomate();
for (i = 0; i <= n - 1; ++i) {
descLente(initial(M), i, &fourche, &k, y, n);
p = fourche;
for (j = k; j <= n - 1; ++j) {
q = nouvelEtat();
fixerCible(p, y[j], q);
p = q;
}
sortie(p) = i;
}
sortie(initial(M)) = n;
return(M);
} |
Partager