/* Fundamental string processing from Gusfield, Algorithms on
   Strings, Trees, and Sequences:  Computer Science and Computational
   Biology, pages 8-10 */
/* Note: C string conventions are used instead of Pascal as in
   Gusfield
   Note: '$' is used as a distinguished character and should not
   be used in input strings to application functions */
/* BPW, 5/2/98 */

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

#define ONE (1)

char S[1001];
int sLength;
int Z[1001];  /* Given a string S and a position i, Z[i] is the length
                of the longest substring of S that starts at i and
                matches a prefix of S. */

void fundamental()
{
int i,k,kprime,l,r,count,betaLength;
char marker[1001];

printf("fundamental: %s\n",S);
sLength=strlen(S);
if (sLength==0)
  return;
Z[0]=sLength;
printf("S[0]='%c': Z[0]=%d\n",S[0],Z[0]);

if (sLength==ONE)
  return;
/* Find Z[1] */
for (i=ONE;S[i]==S[i-ONE];i++)
  ;
Z[ONE]=i-ONE;
printf("S[1]='%c': Z[1]=%d\n",S[ONE],Z[ONE]);
if (Z[ONE]>0)
{
  r=Z[ONE];
  l=ONE;
}
else
  r=l=(-ONE);

/* Find other Z[k] */
for (k=2;k<sLength;k++)
{
  printf("l=%d r=%d\n",l,r);
  printf(" %s\n",S);
  for (i=0;i<=sLength;i++)
    marker[i]=' ';
  marker[i]='\0';
  marker[ONE+l]='<';
  marker[ONE+r]='>';
  marker[ONE+k]='^';
  printf("%s\n",marker);
  if (k>r)
  {
    printf("S[%d]='%c': case 1 (search for mismatch)\n",k,S[k]);
    for (count=0;S[k+count]==S[count];count++)
      ;
    printf("S[%d]='%c': case 1 (Z[%d]=%d)\n",k,S[k],k,count);
    Z[k]=count;
    if (Z[k]>0)
    {
      r=k+Z[k]-ONE;
      l=k;
      printf("S[%d]='%c': case 1 (l=%d r=%d)\n",k,S[k],l,r);
    }
    else
    {
      printf("S[%d]='%c': case 1 (l=-1 r=-1)\n",k,S[k]);
      r=l=(-ONE);
    }
  }
  else /* k<=r */
  {
    kprime=k-l;
    betaLength=r-k+ONE;
    printf("S[%d]='%c': case 2 (Z[kprime=%d]=%d ? betaLength=%d)\n",
      k,S[k],kprime,Z[kprime],betaLength);
    if (Z[kprime]<betaLength)
    {
      printf("S[%d]='%c': case 2a (? is <: Z[%d]=Z[%d]=%d)\n",k,S[k],
        k,kprime,Z[kprime]);
      Z[k]=Z[kprime];
    }
    else /* Z[kprime]>=betaLength */
    {
      for (count=ONE;S[r+count]==S[betaLength+count-ONE];count++)
        ;
      Z[k]=r+count-k;
      r=r+count-ONE;
      l=k;
      printf("S[%d]='%c': case 2b (? is >= scan %d chars Z[%d]=%d l=%d r=%d)\n",
        k,S[k],count,k,Z[k],l,r);
    }
  }
}

/* Print results */
for (i=0;i<sLength;i++)
  printf("%3d %c %3d\n",i,S[i],Z[i]);
}

char *fibPtr;

void fibRecurse(int k)
{
if (k==0)
  (*(fibPtr++))='1';
else if (k==ONE)
  (*(fibPtr++))='0';
else
{
  fibRecurse(k-ONE);
  fibRecurse(k-2);
}
}

void fib(char* target, int k)
{
fibPtr=target;
fibRecurse(k);
(*fibPtr)='\0';
}

void search(char* pattern, char* text)
{
int i,patternLength,textLength;
char marker[1001];

printf("search: pattern=%s text=%s\n",pattern,text);
patternLength=strlen(pattern);
textLength=strlen(text);
strcpy(S,pattern);
S[patternLength]='$';
strcpy(&S[patternLength+ONE],text);
fundamental();
printf("%s   %s\n",text,pattern);
for (i=0;i<textLength;i++)
  marker[i]=' ';
marker[textLength]='\0';
for (i=0;i<textLength;i++)
  if (Z[i+ONE+patternLength]==patternLength)
    marker[i]='^';
printf("%s\n",marker);
}

void circularlyEqual(char* pat1, char* pat2)
{
int i,j,pat1Length,pat2Length;

printf("circularlyEqual? %s %s\n",pat1,pat2);
pat1Length=strlen(pat1);
pat2Length=strlen(pat2);
if (pat1Length!=pat2Length)
{
  printf("%s != %s\n",pat1,pat2);
  return;
}
strcpy(S,pat1);
S[pat1Length]='$';
strcpy(&S[pat1Length+ONE],pat2);
strcpy(&S[pat1Length+ONE+pat2Length],pat2);
fundamental();

for (i=0;i<pat2Length;i++)
  if (Z[i+pat1Length+ONE]==pat1Length)
    break;
if (i==pat2Length)
{
  printf("%s != %s\n",pat1,pat2);
  return;
}
printf("%s %s%s\n",pat1,pat2,pat2);
for (j=0;j<pat1Length+ONE+i;j++)
  printf(" ");
printf("^\n");
}

void prefixSuffix(char* prefixPattern, char* suffixPattern)
{
int i,j,prefixPatternLength,suffixPatternLength;

printf("prefixSuffix: %s %s\n",prefixPattern,suffixPattern);
prefixPatternLength=strlen(prefixPattern);
suffixPatternLength=strlen(suffixPattern);
strcpy(S,prefixPattern);
S[prefixPatternLength]='$';
strcpy(&S[prefixPatternLength+ONE],suffixPattern);
fundamental();

printf("%s %s\n",prefixPattern,suffixPattern);
for (i=0;i<suffixPatternLength;i++)
  if (Z[i+prefixPatternLength+ONE]==suffixPatternLength-i)
    break;
if (i==suffixPatternLength)
{
  printf("no overlap\n");
  return;
}
for (j=0;j<prefixPatternLength+ONE+i;j++)
  printf(" ");
printf("^\n");
}

main()
{
int i;
char pattern[1000],text[1000];

strcpy(S,"0100101001001");
fundamental();
strcpy(S,"abcababcabcababcababc");
fundamental();
strcpy(S,"0100101001001010010100100101001001");
fundamental();
}