#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ALPH_SIZE 2

char *genrandstr ( int m )
{
   char *T;
   int i;

   T = (char *)malloc((m+1) * sizeof(char));
   for (i = 0; i < m; ++i) T[i] = 'a' + (char)(rand() % ALPH_SIZE);
   T[m]= '\0';
   return T;
}

/* The original KMP procedure */
int *calcfailurefn ( char *T, int m )
{
   int *F;
   int i, j;

   F = (int *)malloc(m * sizeof(int));
   F[0] = 0; i = 1; j = 0;
   while (i < m) {
      while ((i < m) && (T[i] == T[j])) {
         ++j; F[i] = j; ++i;
      }

      if (i == m) break;

      if (j == 0) {
         F[i] = 0; ++i;
      } else {
         j = F[j-1];
      }
   }
   return F;
}

/* Calculate the prefix table from the border table */
int *calcpfxtbl ( int *F, int m )
{
   int *G;
   int i, j;

   G = (int *)malloc(m * sizeof(int));
   G[0] = m; for (i=1; i<m; ++i) G[i] = 0;

   for (i = m-1; i > 0; --i) {
      j = F[i];
      while (j > 0) {
         if (G[i-j+1] == 0) {
            G[i-j+1] = j;
         }
         j = F[j-1];
      }
   }
   return G;
}

/* Calculate the border table from the prefix table. This is a linear-time
   algorithm. */
int *recalcfailurefn ( int *G, int m )
{
   int *F;
   int i, j;

   F = (int *)malloc(m * sizeof(int));
   for (j=0; j<m; ++j) F[j] = 0;
   for (i=1; i<m; ++i) {
      j = i + G[i] - 1;
      while ((j >= i) && (F[j] == 0)) {
         F[j] = j-i+1;
         --j;
      }
   }
   return F;
}

void printstr ( char *T, int m )
{
   int i;

   for (i=0; i<m; ++i) printf("%2c", T[i]);
   printf("\n");
}

void printtbl ( int *F, int m )
{
   int i;

   for (i=0; i<m; ++i) printf("%2d", F[i]);
   printf("\n");
}

int main ( int argc, char *argv[] )
{
   int m;
   char *T;
   int *F, *G;

   srand((unsigned int)time(NULL));
   if (argc == 1) exit(1);
   m = atoi(argv[1]);

   T = genrandstr(m);
   // strcpy(T, "aaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaa"); /* Length = 40 */
   // strcpy(T, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"); /* Length = 40 */
   // strcpy(T, "abacabadabacaba"); /* Length = 15 */
   // strcpy(T, "abacabadeabacabadfabacabadeabacabad"); /* Length = 35 */
   // strcpy(T, "abacabadeabacabadfabacabadeabacabadgabacabadeabacabadfabacabadeabacabad"); /* Length = 71 */
   printstr(T,m);

   F = calcfailurefn(T,m);
   free(T);
   printtbl(F,m);

   G = calcpfxtbl(F,m);
   printtbl(G,m);
   free(F);

   F = recalcfailurefn(G,m);
   printtbl(F,m);
   free(G); free(F);

   exit(0);
}