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

#define MAXPATLEN 80
#define MAXCHAR 256
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)

void preprocpat(pat,skip,d)
char *pat;
int skip[],d[];
{
int j,k,m,t,t1,q,q1;
int f[MAXPATLEN];

m=strlen(pat);
for (k=0;k<MAXCHAR;k++)
  skip[k]=m;

for (k=1;k<=m;k++)
{
  d[k-1]=(m<<1) - k;
  skip[pat[k-1]]=m-k;
}

t=m+1;
for (j=m;j>0;j--)
{
  f[j-1]=t;
  while (t<=m && pat[j-1]!=pat[t-1])
  {
    d[t-1]=min(d[t-1],m-j);
    t=f[t-1];
  }
  t--;
}
q=t;
t=m+1-q;
q1=1;
t1=0;
for (j=1;j<=t;j++)
{
  f[j-1]=t1;
  while (t1>=1 && pat[j-1]!=pat[t1-1])
    t1=f[t1-1];
  t1++;
}
while (q<m)
{
  for (k=q1;k<=q;k++)
    d[k-1]=min(d[k-1],m+q-k);
  q1=q+1;
  q+=t-f[t-1];
  t=f[t-1];
}
}

char *search(pat,text,n)
char *pat,*text;
int n;
{
int j,k,m,skip[MAXCHAR],d[MAXPATLEN];

m=strlen(pat);
if (m==0) return text;
preprocpat(pat,skip,d);

for (k=m-1;k<n;k+=max(skip[text[k]&(MAXCHAR-1)],d[j]))
{
  for (j=m-1;j>=0 && text[k]==pat[j];j--)
    k--;
  if (j==(-1)) return text+k+1;
}
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,strlen(text));
  printf("%s\n",text);
  if (pos==NULL)
    printf("Not found\n");
  else
  {
    for (work=text;work<pos;work++)
      printf(" ");
    printf("^\n");
  }
}
}