#include <stdlib.h>
 #include <string.h>
 
 typedef char BIT; /* needs only to hold the values 0 and 1 */
 
 const char *bitap_search(const char *text, const char *pattern)
 {
     const char *result = NULL;
     int m = strlen(pattern);
     BIT *R;
     int i, k;
 
     if (pattern[0] == '\0') return text;
 
     /* Initialize the bit array R */
     R = malloc((m+1) * sizeof *R);
     R[0] = 1;
     for (k=1; k <= m; ++k)
       R[k] = 0;
 
     for (i=0; text[i] != '\0'; ++i) {
         /* Update the bit array. */
         for (k=m; k >= 1; --k)
           R[k] = R[k-1] && (text[i] == pattern[k-1]);
 
         if (R[m]) {
             result = (text+i - m) + 1;
             break;
         }
     }
 
     free(R);
     return result;
 }