/* Determine all possible occurences of pattern string in text
string using KMP technique*/
#include <stdio.h>
#include <string.h>

#define MAXPATLEN 800
#define EOS 0

void preprocpat1(pat,next)
/* Produces slower failure links, but capable of continuing after
   match */
char *pat;
int next[];
{
int i,j;
i=0;
j=next[0]= -1;
do
{
  if (j==(-1)||pat[i]==pat[j])
  {
    i++;
    j++;
    next[i]=j;
  }
  else
    j=next[j];
} while (pat[i]!=EOS);
printf("Fail link table 1\n");
for (i=0;pat[i]!=EOS;i++)
  printf("%d %c %d\n",i,pat[i],next[i]);
}

void preprocpat2(pat,next)
/* Produces faster failure links, but INcapable of continuing after
   match */
char *pat;
int next[];
{
int i,j;
i=0;
j=next[0]= -1;
do
{
  if (j==(-1)||pat[i]==pat[j])
  {
    i++;
    j++;
    next[i]=(pat[j]==pat[i]) ? next[j] : j;
  }
  else
    j=next[j];
} while (pat[i]!=EOS);
printf("Fail link table 2\n");
for (i=0;pat[i]!=EOS;i++)
  printf("%d %c %d\n",i,pat[i],next[i]);
}

void match(text1,pat)
char *text1,*pat;
{
int next1[MAXPATLEN],next2[MAXPATLEN],i,j;
char *text;
char printSymbol=' ';
int restartPosition;

if (*pat==EOS) return;
preprocpat1(pat,next1);
preprocpat2(pat,next2);

j=strlen(pat)-1;
for (restartPosition=next1[j];
     restartPosition!=(-1) && pat[restartPosition]!=pat[j];
     restartPosition=next1[restartPosition])
  ;

text=text1;
printf("Running matcher\n%c ",*text);
for (j=0; *text!=EOS;)
{
  if (j==(-1) || pat[j]== *text)
  {
    if (pat[j+1]==EOS)
    {
      printf("< Match ends here.  Use %d to restart.  ",restartPosition);
      j=restartPosition;  /*restart*/
    }
    else
    {
      printf("%d ",j);
      text++;
      j++;
      printf("\n");
      if (*text!=EOS)
        printf("%c ",*text);
    }
  }
  else
  {
    printf("%d ",j);
    j=next2[j];
  }
}
}

main()
{
char pat[800],text[800];

printf("Enter text & pattern\n");
/*variable text is string 1, variable pat is string 2*/
while (scanf("%s %s",text,pat)!=EOF)
{
  match(text,pat);
  printf("Enter text & pattern\n");
}
}