// meilleur-prefixe.c

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

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

int *meilleurPrefixe(Mot x, Longueur m) {
   int i, j, *meilPref;

   meilPref = (int *)malloc((m + 1)*sizeof(int));
   if (meilPref == NULL) error("meilPrefixes");

   meilPref[0] = -1;
   i = 0;
   for (j = 1; j <= m - 1; ++j) {
      // Ici, x[0..i - 1] = Bord(x[0..j - 1])
      if (x[j] == x[i])
         meilPref[j] = meilPref[i];
      else {
         meilPref[j] = i;
         do {
            i = meilPref[i];
         }
         while (i >= 0 && x[j] != x[i]);
      }
      ++i;
   }
   meilPref[m] = i;
   return(meilPref);
}