Knuth-Moriss-Pratt Algorithm

#include
#include
int F[100],n,m,f=0;
void build_failure_function(char pattern[]){
 // let m be the length of the pattern 
 F[0] = F[1] =0;
 for(int i = 2; i <= m; i++) {
    /*j is the index of the largest next partial match 
    (the largest suffix/prefix) of the string under  
    index i - 1*/
  int j = F[i - 1];
  for( ; ; ) {
   /*check to see if the last character of string i - 
   - pattern[i - 1] "expands" the current "candidate"
   best partial match - the prefix under index j*/
   if(pattern[j] == pattern[i - 1]){ 
    F[i] = j + 1;break; 
   }
   // if we cannot "expand" even the empty string
   if(j == 0){ 
    F[i] = 0;break; 
   }
   // else go to the next best "candidate" partial match
   j = F[j];
  }
 }   
}

void Knuth_Morris_Pratt(char text[], char pattern[]){
 /*let n be the size of the text, m the 
 size of the pattern, and F[] - the
 "failure function"*/
 build_failure_function(pattern);
 int i = 0; // the initial state of the automaton is
       // the empty string
 int j = 0; // the first character of the text
 for( ; ; ) {
  if(j == n) break; // we reached the end of the text
  // if the current character of the text "expands" the
  // current match 
  if(text[j] == pattern[i]) {
   i++; // change the state of the automaton
   j++; // get the next character from the text
   if(i == m){
    f=1;
    printf("match found\n");   
   }
  }
  /*if the current state is not zero (we have not
  reached the empty string yet) we try to
  "expand" the next best (largest) match*/
  else if(i > 0) i = F[i];
  /*if we reached the empty string and failed to
  "expand" even it; we go to the next 
  character from the text, the state of the
  automaton remains zero*/
  else j++;
 }
 if(f==0)
  printf("not found\n");
}

int main()
{
 char s1[100],s2[100];
 gets(s1);
 gets(s2);
 n=strlen(s1);
 m=strlen(s2);
 Knuth_Morris_Pratt(s1, s2);
 return 0;
}