We continue on our journey toward better algorithms for
solving the reed alignment problem.
We studied naive exact matching which was very simple.
It consisted of two nested loops, a loop that iterates over possible alignments and
then a loop that iterates over character comparisons.
Next we will look at an algorithm called Boyer-Moore.
Boyer-Moore is similar to naive exact matching, in some ways.
It's still going to try alignments, and for each alignment,
it will try character comparisons, but it's going to be clever
by skipping many alignments that it doesn't need to examine.
Boyer-Moore is a very popular algorithm.
It's been around for a long time, and
it's really the benchmark exact matching algorithm.
There have been many variants on Boyer-Moore proposed, and
it's implemented in many different systems.
Chances are very good that at some point you have done a search in a web document
or file on your hard drive, and that search was implemented using Boyer-Moore.
So, we'll start with this insight.