// arbre-suffixes-bis.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"
#include "automate.h"


void descLenteBis(Etat p, int k, Etat *resp, int *resk, Mot y, Longueur n, Automate M) {
   Etat e, f, q;

   while (k < n && cible(p, y[k]) != NULL) {
      q = cible(p, y[k]);
      e = p;
      f = q;
      while (e != initial(M) && ls(f) == NULL) {
         ls(f) = cible(ls(e), y[k]);
         e = ls(e);
         f = ls(f);
      }
      if (e == initial(M))
         ls(f) = initial(M);
      p = q;
      ++k;
   }
   *resp = p;
   *resk = k;
}


Automate arbreSuffixesBis(Mot y, Longueur n) {
   Automate M;
   Etat fourche, p, q;
   int i, j, k;

   M = nouvelAutomate();
   fourche = initial(M);
   k = 0;
   for (i = 0; i <= n - 1; ++i) {
      if (k < i)
         k = i;
      descLenteBis(ls(fourche), k, &fourche, &k, y, n, M);
      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);
}