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

#define MAXPATLEN 80
#define EOS 0

void preprocpat(pat,next)
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\n");
for (i=0;pat[i]!=EOS;i++)
  printf("%d %c %d\n",i,pat[i],next[i]);
}

char *search(pat,text)
char *pat,*text;
{
int next[MAXPATLEN],j;

if (*pat==EOS) return text;
preprocpat(pat,next);

for (j=0; *text!=EOS;)
{
  if (j==(-1)||pat[j]== *text)
  {
    text++;
    j++;
    if (pat[j]==EOS) return text-j;
  }
  else
    j=next[j];
}
return NULL;
}

main()
{
char pat[80],text[80],*pos,*work;

printf("Enter pattern & text\n");
while (scanf("%s %s",pat,text)!=EOF)
{
  pos=search(pat,text);
  printf("%s\n",text);
  if (pos==NULL)
    printf("Not found\n");
  else
  {
    for (work=text;work<pos;work++)
      printf(" ");
    printf("^\n");
  }
}
}