/*********************************************************  
  TD d'Algorithmique IN202 
  ENSTA  
 
  Mardi 12 Decembre 2000   
   
  Pattern-matching: automate de recherche  
   
                                        Guillaume Poupard  
*********************************************************/ 
#include <stdio.h>  
#include <stdlib.h> 
#include <string.h>  
 
int d=2;  
 
int **calcul_automate(char *P)  
{ 
  int m=strlen(P);  
  int **delta; 
  char *Pr;  
  char *Pqx; 
  int i,j,k;  
 
  Pr=(char *)malloc(sizeof(char)*m);  
  Pqx=(char *)malloc(sizeof(char)*m); 
    
  delta=(int **) malloc(sizeof(int *)*m); 
  for(i=0;i<m;i++)  
    delta[i]=(int *) malloc(sizeof(int)*d); 
  for(i=0;i<m;i++)  
    for(j=0;j<d;j++) 
      {  
        strncpy(Pr,P,i+1); 
        Pr[i+1]='\0';
        strncpy(Pqx,P,i); 
        Pqx[i]=j+'a';  
        Pqx[i+1]='\0'; 
        k=i+1;  
        while (strcmp(Pr,Pqx+i+1-k)!=0) 
          {  
            k--; 
            Pr[k]='\0';  
          } 
        printf("delta(%d,%c)=%d\n",i,j+'a',k);  
        delta[i][j]=k; 
      }  
  free(Pr); 
  free(Pqx);  
  return delta; 
}  
     
    
int recherche(int **delta, char *P, char *T) 
{  
  int n=strlen(T); 
  int m=strlen(P);  
  int s; 
  int q=0;  
  for(s=0;s<n;s++) 
    {  
      q=delta[q][T[s]-'a']; 
      if (q==m)  
        return 1; 
    }  
  return 0; 
}  
   
int main(int argc, char * argv[])  
{ 
  int **delta=calcul_automate("aabba");  
  printf("%d\n",recherche(delta,"aabba","ababbabaaabbababbabbbbababa")); 
  printf("%d\n",recherche(delta,"aabba","ababbabaaabababababbbbababa"));  
  exit(0); 
}