The Boyer-Moore algorithm
As we have already discussed, the main objective of the string pattern matching algorithm is to find ways of skipping comparisons as much as possible by avoiding unnecessary comparisons.
The Boyer-Moore pattern matching algorithm is another such algorithm (along with the KMP algorithm) that further improves the performance of pattern matching by skipping comparisons using different methods. We have to understand the following concepts in order to understand the Boyer-Moore algorithm:
- In this algorithm, we shift the pattern in the direction from left to right, similar to the KMP algorithm.
- We compare the characters of the pattern and the text string from right to left, which is the opposite of what we do in the case of the KMP algorithm.
- The algorithm skips the unnecessary comparisons by using the good suffix and bad character shift heuristics. These heuristics themselves find the possible number of comparisons that can be skipped...
