The Boyer-Moore string searching algorithm was introduced by Robert S. Boyer and J. Strother Moore in 1977, and builds upon the naive search algorithm by intelligently skipping certain sections of the text.

One key feature of the algorithm is that it matches the pattern from right to left, instead of left to right, using to its advantage a couple of shift rules that improve its running time. To understand the effect of these rules, let's build the Boyer-Moore algorithm from our naive search algorithm.

We'll start by modifying the matching on the pattern so that it operates from right to left. The following code demonstrates this:

for (int j = m - 1; j >= 0; j--) {
  if (P.charAt(j) != T.charAt(i + j)) {
    hasMatch = false;
    break;
  }
}

Snippet 5.2: Modifying the inner loop from Snippet 5.1 for algorithm to operate from right to left C

Using the naive string matching algorithm as the base, let's look at some rules that allow...