/*********************************************************  
  TD d'Algorithmique IN202   
  ENSTA  
   
  Mardi 12 Decembre 2000   
    
  Pattern-matching: Algorithme de Rabin et Karp  
     
                                        Guillaume Poupard  
*********************************************************/   
#include <stdio.h>  
#include <stdlib.h>   
#include <string.h>  
   
char Texte[]="abbaabbbabaabbb";  
int d=2;   
  
int expo(int a, int b)   
{  
  int p=1;   
  while (b>0)  
    {   
      if ((b%2)==1)  
        p=p*a;   
      a=a*a;  
      b=b/2;   
    }  
  return p;   
}  

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);   
  for(j=0;j<m;j++)  
    t+=(T[j]-'a')*expo(d,m-1-j);   
  
   
  for(s=0;s<=n-m-1;s++)  
    {   
      if (p==t)  
        return 1;   
      t=(t-(T[s]-'a')*h)*d+(T[s+m]-'a'); 
    }  
  if (p==t) 
    return 1;  
  return 0; 
}  
   
  
 
int main(int argc, char * argv[])  
{ 
  printf("%d\n",recherche("baaba",Texte));  
  printf("%d\n",recherche("baba",Texte)); 
  printf("%d\n",recherche("baab",Texte));  
  exit(0); 
}