#include <string.h>

int
boyer_moore(const char *hs,   /* haystack string */
            int hc,           /* sizeof haystack */
            int hp,           /* start of search position */
            const char *ns,   /* needle string */
            int nc) {         /* sizeof needle */
  int skiptable[256];
  int idx;
  int skip;
  const char *cs;
  const char *ce;
  int nlen_minus_1;

  /* initialize skiptable to length of needle */
  for(idx=0; idx<256; ++idx)
    skiptable[idx] = nc;
  /* skiptable[idx] = last index of codepoint[idx]
     in needle */
  nlen_minus_1 = nc - 1;
  cs = ns;
  for(idx=nlen_minus_1; idx>0; --idx)
    skiptable[*cs++] = idx;

  cs = hs;
  ce = hs + hc;

  while( cs < ce ) {
    idx = nlen_minus_1;
    while( idx >= 0 && ns[idx] == cs[idx] )
      --idx;
    if(idx > 0) {
      /* MISMATCH */
      int add;
      skip = skiptable[cs[idx]];
      if(skip!=nc) {
        /* GOOD SUFFIX */
        add = idx + skip - nlen_minus_1;
        if(add<0)
          add = 1;
      } else
        /* BAD CHAR */
        add = idx + 1;
      cs += add;
    } else {
      idx = (int)(cs - hs);
      goto finished;
    }
  }
  idx = -1;
finished:
  return idx;
}


int
main(void) {
#define TEST(HAY,POS,NDL) do {                                       \
  const char *hay = (HAY);                                           \
  const char *ndl = (NDL);                                           \
  int haylen = strlen(hay);                                          \
  int ndllen = strlen(ndl);                                          \
  int pos = (POS);                                                   \
  pos = boyer_moore(hay,haylen,pos,                                  \
                    ndl,ndllen);                                     \
  if(pos<0)                                                          \
    printf("<%s> not found in <%s>\n", ndl, hay + (POS));            \
  else                                                               \
    printf("<%s> found in <%s> at position %d\n", ndl, hay, pos);    \
} while(0)

  TEST("MEOW", 0, "OW");
  TEST("OOOPSOOOPSDOO", 0, "OOPS");
  TEST("xxxxBooooxxxx", 2, "Boooo");
  return 0;
}