/********************************************************* 
  TD d'Algorithmique IN202  
  ENSTA 
  
  Mardi 12 Decembre 2000  
  
  Pattern-matching: Algorithme de Rabin et Karp (2) 
    
                                        Guillaume Poupard 
*********************************************************/  
#include <stdio.h> 
#include <stdlib.h>  
#include <string.h> 
  
char Texte[]="bonjourlaterre"; 
int d=26;  
int q=65521; 
  
int expo(int a, int b) 
{  
  int p=1; 
  while (b>0)  
    { 
      if ((b%2)==1)  
        p=(p*a)%q; 
      a=a*a;  
      b=b/2; 
    }  
  return p; 
}  
 
int decalage_valide(char *P, char *T, int s)  
{ 
  int i;  
  int m=strlen(P); 
    
  for(i=0;i<m;i++) 
    if (P[i]!=T[i+s])  
      return 0; 
  return 1;
} 
  
int recherche(char *P, char *T) 
{  
  int n=strlen(T); 
  int m=strlen(P);  
  int s; 
  int h=expo(d,m-1);  
  int p=0; 
  int t=0;  
  int j; 
    
  for(j=0;j<m;j++) 
    p+=((P[j]-'a')*expo(d,m-1-j)) % q;  
  for(j=0;j<m;j++) 
    t+=((T[j]-'a')*expo(d,m-1-j)) % q;  
 
  for(s=0;s<=n-m-1;s++)  
    { 
      if (p==t)  
        if (decalage_valide(P,T,s)) 
          return 1;  
      t=((((t-(T[s]-'a')*h)*d+(T[s+m]-'a')) % q)+q) %q; 
    }  
  if (p==t) 
    if (decalage_valide(P,T,s))  
        return 1; 
  return 0;  
} 
    
 
  
int main(int argc, char * argv[]) 
{  
  printf("%d\n",recherche("bonjour",Texte)); 
  printf("%d\n",recherche("terr",Texte));  
  printf("%d\n",recherche("late",Texte)); 
  printf("%d\n",recherche("bonx",Texte));  
  printf("%d\n",recherche("terrex",Texte)); 
  exit(0);  
}