Algorithme de Boyer-Moore - Définition

      #include       #include              static inline ssize_t max(ssize_t a, ssize_t b) { return a > b ? a : b; }             /* This helper function checks, whether the last "portion" bytes       * of "needle" (which is "nlen" bytes long) exist within the "needle"       * at offset "offset" (counted from the end of the string),       * and whether the character preceding "offset" is not a match.       * Notice that the range being checked may reach beyond the       * beginning of the string. Such range is ignored.       */      static inline int boyermoore_needlematch(          const unsigned char* needle, size_t nlen,          size_t portion, size_t offset)      {          ssize_t virtual_begin = nlen - offset - portion;          ssize_t ignore = 0;                 if (virtual_begin < 0) {              ignore = -virtual_begin;              virtual_begin = 0;          }          if (virtual_begin > 0 && needle[virtual_begin - 1] == needle[nlen-portion - 1])              return 0;          return memcmp(              needle + nlen - portion + ignore,              needle + virtual_begin,              portion - ignore) == 0;      }              /* Returns a pointer to the first occurrence of "needle"       * within "haystack", or NULL if not found.       */      const unsigned char* memmem_boyermoore(          const unsigned char* haystack, size_t hlen,          const unsigned char* needle,   size_t nlen)      {          size_t *skip; /* Array of shifts with self-substring match check */          size_t a, hpos;          ssize_t occ[UCHAR_MAX + 1]; /* Array of last occurrence of each character */                 if (nlen > hlen || nlen <= 0 || !haystack || !needle)              return NULL;                 /* Preprocess #1: init occ[] */          /* Initialize the table to default value */          for (a = UCHAR_MAX + 1; --a >= 0)              occ[a] = -1;          /* Then populate it with the analysis of the needle */          /* But ignoring the last letter */          for (a = 0 ; a < nlen - 1 ; a++)              occ[needle[a]] = a;                 /* Preprocess #2: init skip[] */            /* Note: This step could be made a lot faster.           * A simple implementation is shown here. */          skip = (size_t *) malloc(nlen * sizeof(size_t));          /* We should check here if skip is NULL (allocation failed) ! */          for (a = 0; a < nlen; ++a) {              size_t value = 0;              while (value < nlen && !boyermoore_needlematch(needle, nlen, a, value))                  ++value;              skip[nlen - a - 1] = value;          }                 /* Search */          for (hpos = 0; hpos <= hlen - nlen; ) {              size_t npos = nlen - 1;              while (needle[npos] == haystack[npos + hpos]) {                  if (npos == 0) {                      free(skip);                      return haystack + hpos;                  }                  --npos;              }              hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);          }          free(skip);          return NULL;      }