// 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);
}