Pattern Matching (String)

Boyer-Moore Algorithm

This does the fastest pattern matching on English text.

Important components:

• Reverse-order searching: Compare $P$ with a guess moving backwards When a mismatch occurs, choose the better of the following two options:
• Bad character jumps: Eliminate guesses based on mismatched characters of $T$.
• Good suffix jumps: Eliminate guesses based on matched suffix of $P$.