// suffixes.c

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

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

int *suffixes(Mot x, Longueur m) {
   int f, g, i, *suff;

   suff = (int *)malloc(m*sizeof(int));
   if (suff == NULL) error("suffixes");

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