The Boyer-Moore algorithm is a pattern matching algorithm with a worst-case complexity of , but runs in sublinear time on average, making it highly efficient for many applications.
Although slower in the worst case than the Z-algorithm, Boyer-Moore is generally faster due to its skipping mechanisms.
Overview Of The Boyer-Moore Algorithm
The Boyer-Moore algorithm aligns the pattern with the text and checks for a complete match at each alignment. After a complete match, or a mismatch, the pattern is shifted to the right with respect to the text, generating a new alignment.
To improve upon the naive exact pattern matching method, Boyer-Moore incorporates three key techniques:
- Right-To-Left Scanning
- The Bad Character Shift Rule
- The Good Suffix Shift Rule
Right-To-Left Scanning
Given an alignment of pat[1...m] with txt[j...j+m-1], the Boyer-Moore algorithm compares characters in a right-to-left scan. The comparison starts with pat[m] against txt[j+m-1], followed by pat[m-1] with txt[j+m-2], and continues moving leftward until a mismatch or a complete match is found.
This backward scanning does not, by itself, provide a performance advantage over the left-to-right scanning used in naive methods. However, it is crucial because it enables the Bad Character Rule and Good Suffix Rule, which are responsible for the algorithm’s efficiency.
Example Of Left-To-Right Scanning
