// bon-prefixe.c

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

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

int *bonPrefixe(Mot x, Longueur m) {
   int i, j, *bonPref;

   bonPref = (int *)malloc((m + 1)*sizeof(int));
   if (bonPref == NULL) error("bonPrefixes");

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