#include <limits.h>
#include <stddef.h>
#define ALPHABET_SIZE (1 << CHAR_BITS) /* typically 256 */
/* Preprocessing: the BMH bad-match table. */
static inline void preBmBc(char *pat, size_t lpat, ptrdiff_t bmBc[]) {
size_t i;
for (i = 0; i < ALPHABET_SIZE; ++i)
bmBc[i] = lpat;
for (i = 0; i < lpat - 1; ++i)
bmBc[pat[i]] = lpat - i - 1;
}
void RAITA(char *pat, size_t lpat, char *s, size_t n) {
ptrdiff_t bmBc[ALPHABET_SIZE];
/* Quick edge cases. */
if (lpat == 0 || lpat > n)
return;
if (lpat == 1) {
char *match_ptr = s;
while (match_ptr < s + n) {
match_ptr = memchr(match_ptr, pat[0], n - (match_ptr - s));
if (match_ptr != NULL) {
OUTPUT(match_ptr - s);
match_ptr++;
} else
return;
}
}
preBmBc(pat, lpat, bmBc);
/* The prematch-window. */
char firstCh = pat[0];
char middleCh = pat[lpat / 2];
char lastCh = pat[lpat - 1];
/* Searching */
ptrdiff_t j = 0;
while (j <= n - m) {
char c = s[j + lpat - 1];
/* This could harm data locality on long patterns. For these consider reducing
* the number of pre-tests, or using more clustered indices. */
if (lastCh == c && middleCh == s[j + lpat / 2] && firstCh == s[j] &&
memcmp(&pat[1], &s[j+1], lpat - 2) == 0)
OUTPUT(j);
j += bmBc[c];
}
}