/* Determine all possible overlaps for two strings*/
#include <stdio.h>
#include <string.h>

#define MAXPATLEN 80
#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 overlap(text1,pat)
char *text1,*pat;
{
int next1[MAXPATLEN],next2[MAXPATLEN],i,j;
char *text;

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

text=text1;
for (j=0; *text!=EOS;)
  if (j==(-1)||pat[j]== *text)
    if (pat[j+1]==EOS && *(text+1)!=EOS)
      j=next1[j];  /*restart*/
    else
    {
      text++;
      j++;
    }
  else
    j=next2[j];

printf("%s\n",text1);
for (i=0;i<strlen(text1)-j;i++)
  printf(" ");
printf("%s\n",pat);
if (j<=0)
  return;
j=next1[j-1];
while (j>(-1))
{
  if (*(text-1)==pat[j])
  {
    for (i=0;i<strlen(text1)-j-1;i++)
      printf(" ");
    printf("%s\n",pat);
  }
  j=next1[j];
}
}

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

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