Search

0.2.6.1 Source Code

#include 
 #include 
 #include 
 #include 
 
 #define alphabet_size (UCHAR_MAX + 1)
 
 #ifndef max
   #define max(a,b)	((a) > (b) ? (a) : (b))
 #endif
 
 char *boyer_moore_search (char *target, char *text, size_t length) {
   unsigned char_jump[alphabet_size];
   unsigned *match_jump;
   unsigned *backup;
   size_t pat_len;
   unsigned u, u_text, u_pat, ua, ub;
 
   pat_len = strlen(target);
   match_jump = (unsigned *) malloc (2 * sizeof(unsigned) * (pat_len + 1));
   backup = match_jump + pat_len + 1;
 
   /* heuristic #1 setup, simple text search */
 
   memset (char_jump, 0, alphabet_size * sizeof(unsigned));
   for (u = 0; u < pat_len; u++)
     char_jump[((unsigned char) target[u])] = pat_len - u - 1;
 
 
 
   /* heuristic #2 setup, repeating pattern search */
 
   for (u = 1; u <= pat_len; u++)
     match_jump[u] = 2 * pat_len - u;
 
   u = pat_len;
   ua = pat_len + 1;
   while (u > 0) {
     backup[u] = ua;
     while (ua <= pat_len && target[u - 1] != target[ua - 1]) {
       if (match_jump[ua] > pat_len - u) match_jump[ua] = pat_len - u;
       ua = backup[ua];
     }
     u--; ua--;
   }
 
   for (u - 1; u <= ua; u++)
     if (match_jump[u] > pat_len + ua - u) match_jump[u] = pat_len + ua - u;
 
   ub = backup[ua];
   while (ua <= pat_len) {
     while (ua <= ub) {
       if (match_jump[ua] > ub - ua + pat_len)
 	match_jump[ua] = ub - ua + pat_len;
       ua++;
     }
     ub = backup[ub];
   }
 
 
   /* perform search */
   u_pat = pat_len;
   u_text = pat_len - 1;
   while (u_text < text_len && u_pat != 0) {
     if (text[u_text] == target[u_pat - 1]) {
       u_text--;
       u_pat--;
     } else {
       ua = char_jump[((unsigned char) text[u_text])];
       ub = match_jump[u_pat];
       u_text += max(ua, ub);
       u_pat = pat_len;
     }
   }
 
   if (u_pat == 0) {
     return((char *) (text + (u_text + 1)));
   } else {
     return(NULL);
   }
 }