Boyer Moore String Matching Algorithm
Boyer Moore is another string matching algorithm that is going to be discussed in this series of string matching algorithms. Boyer moore works on two methods, bad match table and good suffix heuristics. In this post, I will discuss an implementation of the bad match table.
What Boyer moore does, basically in the case of a mismatch is compare the currently mismatched character in the text and skip to the apt position as defined in the bad match table. This means that we need to create a bad match table, which means preprocessing the pattern. This is achieved in a linear time with O(m) space, for a pattern P[0…m] and text T[0…n]. After the pattern preprocessing, each character is checked from right to left as opposed to conventional directions in both KMP and Naive String matching algorithms. If the mismatched character in the text is not in the pattern, then it means that we need to skip the pattern to a new position to just right of the mismatched character.
The images above illustrate the algorithm in a concise way.
Time Complexity: O(mn) worst case, O(n/m) Best case.
Here is a sample implementation of the algorithm:
