// 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); }