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

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

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

int hpat,htext,Bm,j,m;

if (pat[0]==EOS) return;
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];
  printf("%c ",text[m]);
  if (pat[m+1]==EOS)
    printf("%d",htext);
  else
    printf("\n");
}

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

for (j=m;TRUE;j++)
{
  if (hpat==htext && strncmp(text+j-m,pat,m)==0)
    printf("<<<\n");
  else
    printf("\n");
  if (text[j]==EOS) return;
  htext=htext*B-text[j-m]*Bm+text[j];
  printf("%c %d ",text[j],htext);
}
}

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

printf("Enter pattern & text\n");
while (scanf("%s %s",pat,text)!=EOF)
{
  search(pat,text);
  printf("Enter pattern & text\n");
}
}