// auto-suffixes.c

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

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

void extension(Lettre a, Automate M) {
   Etat clone, nouveau, p, q;

   nouveau = nouvelEtat();
   L(nouveau) = L(dernier(M)) + 1;
   p = dernier(M);
   do {
      fixerCible(p, a, nouveau);
      p = F(p);
   }
   while (p != NULL && cible(p, a) == NULL);
   if (p == NULL)
      F(nouveau) = initial(M);
   else {
      q = cible(p, a);
      if (L(p) + 1 == L(q))
         F(nouveau) = q;
      else {
         clone = nouvelEtat();
         L(clone) = L(p) + 1;
         copieCibles(clone, q);
         F(nouveau) = clone;
         F(clone) = F(q);
         F(q) = clone;
         do {
            fixerCible(p, a, clone);
            p = F(p);
         }
         while (p != NULL && cible(p, a) == q);
      }
   }
   dernier(M) = nouveau;
}


Automate autoSuffixes(Mot y, Longueur n) {
   Automate M;
   Etat p;

   M = nouvelAutomate();
   L(initial(M)) = 0;
   F(initial(M)) = NULL;
   dernier(M) = initial(M);
   for (; *y != '\0'; ++y)
      // Extension de M par la lettre *y
      extension(*y, M);
   p = dernier(M);
   do {
      terminal(p) = VRAI;
      p = F(p);
   }
   while (p != NULL);
   return(M);
}