// Demonstrates Longest Common Prefix based manipulations for suffix arrays
// 6/1/07 BPW

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

char s[1000000];
int n,           // length of s[] including \0
  sa[1000000],   // suffix array for s[]
  rank[1000000], // rank[i] gives the rank (subscript) of s[i] in sa[]
  lcp[1000000];  // lcp[i] indicates the number of identical prefix symbols
                 // for s[sa[i-1]] and s[sa[i]]

int suffixCompare(const void *xVoidPt,const void *yVoidPt)
{
// Used in qsort call to generate suffix array.
int *xPt=(int*) xVoidPt,*yPt=(int*) yVoidPt;

return strcmp(&s[*xPt],&s[*yPt]);
}

void computeRank()
{
// Computes rank as the inverse permutation of the suffix array
int i;

for (i=0;i<n;i++)
  rank[sa[i]]=i;
}

void computeLCP()
{
//Kasai et al linear-time construction
int h,i,j,k;

h=0;  // Index to support result that lcp[rank[i]]>=lcp[rank[i-1]]-1
for (i=0;i<n;i++)
{
  k=rank[i];
  if (k==0)
    lcp[k]=(-1);
  else
  {
    j=sa[k-1];
    // Attempt to extend lcp
    while (i+h<n && j+h<n && s[i+h]==s[j+h])
      h++;
    lcp[k]=h;
  }
  if (h>0)
    h--;  // Decrease according to result
}
}

int slowSearch(char* key)
{
// Finds string assisted by binary search on suffix array,
// but without using lcp.
int low,high,mid;
//int cmpCount=0;
int i,j;

low=0;
high=n-1;
while (low<=high)
{
  mid=(low+high)/2;
  j=sa[mid]; // Position in s
  i=0;       // Position in key
  //cmpCount++;
  // Like strcmp
  while (s[j]==key[i] && key[i])
  {
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0)
  {
    //printf("slowSearch used %d char comparisons\n",cmpCount);
    return mid; // key found
  }
  if (s[j]<key[i])
    low=mid+1;
  else
    high=mid-1;
}

//printf("slowSearch used %d char comparisons\n",cmpCount);
return (-1); // key does not appear
}

int slowSearchFirst(char* key)
{
// Finds  first string >= key assisted by binary search on suffix array,
// but without using lcp.
int low,high,mid;
//int cmpCount=0;
int i,j;

low=0;
high=n-1;
while (low<=high)
{
  mid=(low+high)/2;
  j=sa[mid]; // Position in s
  i=0;       // Position in key
  //cmpCount++;
  // Like strcmp
  while (s[j]==key[i] && key[i])
  {
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0 || s[j]>key[i])
    high=mid-1;
  else
    low=mid+1;
}

//printf("slowSearchFirst used %d char comparisons\n",cmpCount);
return low;
}

int slowSearchLast(char* key)
{
// Finds last string <= key assisted by binary search on suffix array,
// but without using lcp.
int low,high,mid;
//int cmpCount=0;
int i,j;

low=0;
high=n-1;
while (low<=high)
{
  mid=(low+high)/2;
  j=sa[mid]; // Position in s
  i=0;       // Position in key
  //cmpCount++;
  // Like strcmp
  while (s[j]==key[i] && key[i])
  {
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0 || s[j]<key[i])
    low=mid+1;
  else
    high=mid-1;
}

//printf("slowSearchLast used %d char comparisons\n",cmpCount);
return high;
}

int fastSearch(char* key)
{
// Finds string assisted by binary search on suffix array.
// Uses lcp to limit char comparisons.
int low,high,mid;
//int cmpCount=0;
int i,j;
int keyLength,lowMatches,highMatches,midMatches;

keyLength=strlen(key);
low=0;
lowMatches=0;
high=n-1;
highMatches=0;

while (low<=high)
{
  mid=(low+high)/2;
  // How many strcmp matches can be salvaged?
  midMatches=(lowMatches<highMatches) ? lowMatches : highMatches;

  if (midMatches==keyLength)
  {
    //printf("fastSearch used %d char comparisons\n",cmpCount);
    return mid; // key found
  }

  j=sa[mid]+midMatches; // Position in s
  i=midMatches;         // Position in key
  //cmpCount++;
  // Like strcmp
  while (s[j]==key[i] && key[i])
  {
    midMatches++;
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0)
  {
    //printf("fastSearch used %d char comparisons\n",cmpCount);
    return mid; // key found
  }
  if (s[j]<key[i])
  {
    low=mid+1;
    lowMatches=(lcp[low]<midMatches) ? lcp[low] : midMatches;
  }
  else
  {
    high=mid-1;
    highMatches=(lcp[mid]<midMatches) ? lcp[mid] : midMatches;
  }
}

//printf("fastSearch used %d char comparisons\n",cmpCount);
return (-1); // key does not appear
}

int fastSearchFirst(char* key)
{
// Finds first string >= key assisted by binary search on suffix array.
// Uses lcp to limit char comparisons.
int low,high,mid;
//int cmpCount=0;
int i,j;
int keyLength,lowMatches,highMatches,midMatches;

keyLength=strlen(key);
low=0;
lowMatches=0;
high=n-1;
highMatches=0;

while (low<=high)
{
  mid=(low+high)/2;
  // How many strcmp matches can be salvaged?
  midMatches=(lowMatches<highMatches) ? lowMatches : highMatches;

  if (midMatches==keyLength)
  {
    high=mid-1;
    highMatches=(lcp[mid]<midMatches) ? lcp[mid] : midMatches;
  }

  j=sa[mid]+midMatches; // Position in s
  i=midMatches;         // Position in key
  //cmpCount++;
  while (s[j]==key[i] && key[i])
  {
    midMatches++;
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0 || s[j]>key[i])
  {
    high=mid-1;
    highMatches=(lcp[mid]<midMatches) ? lcp[mid] : midMatches;
  }
  else
  {
    low=mid+1;
    lowMatches=(lcp[low]<midMatches) ? lcp[low] : midMatches;
  }
}

//printf("fastSearchFirst used %d char comparisons\n",cmpCount);
return low;
}

int fastSearchLast(char* key)
{
// Finds last string <= key assisted by binary search on suffix array.
// Uses lcp to limit char comparisons.
int low,high,mid;
//int cmpCount=0;
int i,j;
int keyLength,lowMatches,highMatches,midMatches;

keyLength=strlen(key);
low=0;
lowMatches=0;
high=n-1;
highMatches=0;

while (low<=high)
{
  mid=(low+high)/2;
  // How many strcmp matches can be salvaged?
  midMatches=(lowMatches<highMatches) ? lowMatches : highMatches;

  if (midMatches==keyLength)
  {
    low=mid+1;
    lowMatches=(lcp[low]<midMatches) ? lcp[low] : midMatches;
  }

  j=sa[mid]+midMatches; // Position in s
  i=midMatches;         // Position in key
  //cmpCount++;
  while (s[j]==key[i] && key[i])
  {
    midMatches++;
    j++;
    i++;
    //cmpCount++;
  } 
  if (key[i]==0 || s[j]<key[i])
  {
    low=mid+1;
    lowMatches=(lcp[low]<midMatches) ? lcp[low] : midMatches;
  }
  else
  {
    high=mid-1;
    highMatches=(lcp[mid]<midMatches) ? lcp[mid] : midMatches;
  }
}

//printf("fastSearchLast used %d char comparisons\n",cmpCount);
return high;
}

int fibIndex=0;

void fib(k)
int k;
{
if (k==0)
  s[fibIndex++]='1';
else if (k==1)
  s[fibIndex++]='0';
else
{
  fib(k-1);
  fib(k-2);
}
}

main()
{
int i,j,k,p;
char key[1000000];

int slowCount=0,fastCount=0;

scanf("%s",s);

/*
fib(16);
s[fibIndex]='\0';
*/

/*
for (i=0;i<1000;i++)
  s[i]='a';
s[1000]='b';
s[1001]='\0';
*/
/*
s[0]='a';
for (i=1;i<1000;i++)
  s[i]='b';
s[1000]='\0';
*/

n=strlen(s)+1;
printf("n is %d\n",n);

// Quick-and-dirty suffix array construction
for (i=0;i<n;i++)
  sa[i]=i;
qsort(sa,n,sizeof(int),suffixCompare);
computeRank();
computeLCP();
if (n<200)
{
  printf("i   sa  suffix                              lcp s rank lcp[rank]\n");
  for (i=0;i<n;i++)
    printf("%-3d %-3d %-35.35s %-3d %c  %-3d  %-3d\n",
      i,sa[i],&s[sa[i]],lcp[i],s[i],rank[i],lcp[rank[i]]);
}

while (1)
{
  scanf("%s",&key);
  i=fastSearchFirst(key);
  printf("fastSearchFirst returned %d\n",i);
  i=fastSearchLast(key);
  printf("fastSearchLast returned %d\n",i);
}

/*
for (i=0;i<n;i++)
  for (j=i;j<n;j++)
  {
    p=0;
    for (k=i;k<=j;k++)
      key[p++]=s[k];
    key[p]='\0';
    k=slowSearchLast(key);
    p=fastSearchLast(key);
    if (k!=p)
    {
      printf("Results %d %d inconsistent\n",k,p);
      exit(0);
    }
  }
*/

/*
for (i=0;i<n;i++)
  for (j=i;j<n;j++)
  {
    p=0;
    for (k=i;k<=j;k++)
      key[p++]=s[k];
    key[p]='\0';
    k=slowSearchLast(key)-slowSearchFirst(key);
    p=fastSearchLast(key)-fastSearchFirst(key);
    if (k!=p)
    {
      printf("Results %d %d inconsistent\n",k,p);
      exit(0);
    }
  }
*/
}