
 ------------------------------------------------------------------
     BMHR ~ Boyer-Moore-Horspool-Raita string search algorithm
 ------------------------------------------------------------------

   Implementation of the Boyer-Moore-Horspool (BMH) algorithm.
   BMH is based on/related to the Knuth-Morris-Pratt algorithm.
   This implementation uses a variant of the Raita optimization.

   The Boyer-Moore (BM) algorithm positions the pattern over the
   leftmost characters in the text and attempts to match it from
   right-to-left. If no mismatch occurs the pattern has been found.

   Otherwise, the algorithm computes a shift, the amount by which
   the pattern is moved to the right before a new matching attempt
   is undertaken.

   The shift is computed with the occurrence heuristic, and uses
   a simplification which was proposed in 1980 by Horspool. In
   that paper it was pointed out that any character from the text
   read since the last shift can be used for the alignment.

   To maximize the average shift after a mismatch, the character
   compared with the last character of the pattern is chosen for
   the alignment.

   The occurrence heuristic aligns the right-most tested character
   in the text with the first character (from the right) of the
   pattern matching it, or moves the pattern past it if it does
   not exist in the pattern.

   The shift table is populated prior to the search operation with
   offsets of the characters occurring in the pattern.

   This also implies that the comparisons can be done in any order
   (left-to-right, right-to-left, random, etc). An optimization
   proposed by Tim Raita takes advantage of this by not comparing
   characters sequentially (right-to-left), but right-left-middle.

   The Raita optimization minimizes wasted processing time by
   identifying mismatches more quickly.

 ------------------------------------------------------------------

The Boyer-Moore-Horspool algorithm.

/* Search pat[l. .m] in text[l..n] */

 bmhSearch(text, n, pat, m)
  char text[], pat[]
  int n, m
  {
   int d[ALPHABET_SIZE], i, j, k

 /* preprocess */
   for( j = 0; j < ALPHABET_SIZE; j++ ) d[j] = m
   for( j = 0; j < m - 1; j++ ) d[pat[j]] = m - 1 - j

 /* Search */
   for( i = m; i <= n; i += d[text[i]] )
    {
    k = i
    for( j = m; j > 0 && (text[k] == pat[j]); j-- ) k--
    if( j == 0 ) Report_match_at_position( k + 1 )
    }
  }

 ------------------------------------------------------------------
