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

#define B 131
#define EOS 0
#define TRUE 1
#define FALSE 0

char *search(pat,text)
char *pat,*text;
{

int hpat,htext,Bm,j,m;

if (pat[0]==EOS) return text;
Bm=1;
hpat=htext=0;

for (m=0;text[m]!=EOS && pat[m]!=EOS;m++)
{
  Bm*=B;
  hpat=hpat*B+pat[m];
  htext=htext*B+text[m];
}

if (text[m]==EOS && pat[m]!=EOS) return NULL;

for (j=m;TRUE;j++)
{
  if (hpat==htext && strncmp(text+j-m,pat,m)==0)
    return text+j-m;
  if (text[j]==EOS) return NULL;
  htext=htext*B-text[j-m]*Bm+text[j];
}
}

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