// prefixes.c

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

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

int *prefixes(Mot x, Longueur m) {
   int f, g, i, *pref;

   pref = (int *)malloc(m*sizeof(int));
   if (pref == NULL) error("prefixes");

   pref[0] = m;
   g = 0;
   for (i = 1; i <= m - 1; ++i)
      if (i < g && pref[i - f] < g - i)
         pref[i] = pref[i - f];
      else {
         if (i > g) g = i;
         f = i;
         while (g < m && x[g] == x[g - f])
            ++g;
         pref[i] = g - f;
      }
   return(pref);
}