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

char pattern[100];
int psize;
int next[100];
int fail[100];
int i,j;



void scan(char pattern[]){
   int i;
   int t;
   i=0;
   t=-1;
   fail[0]=-1;
   next[0]=-1;
   do {
      while ((t>=0) && (pattern[i] != pattern[t]))
         t=next[t];
      i++;
      t++;
      fail[i]=t;
      if (pattern[i] == pattern[t])
         next[i] = next[t];
      else
         next[i] = t;
   } while (i < (psize -1));
}


void main (){

   printf("Enter an input string:");
   scanf("%s",pattern);
   psize = strlen(pattern);
   printf("\n\n");
   printf("Pattern length is:%d\n",psize);

   scan(pattern);

   for (i=0; i<psize; i++) {  /*Adjust next and fail to conform to array starting at 1*/
      fail[i]++;
      next[i]++;
   }

   printf("STATE is:");
   for (i=1; i<=psize; i++)
      printf("%3d ",i);
   printf("\n");

   printf("Pattern :");
   for (i=0; i<psize; i++)
      printf("  %c ",pattern[i]);
   printf("\n");

   printf("___________________________________________________\n");

   printf("fail is :");
   for (i=0; i<psize; i++)
      printf("%3d ",fail[i]);
   printf("\nnext is :");
   for (i=0; i<psize; i++)
      printf("%3d ",next[i]);
   printf("\n");
 

}