There are a lot of efficient string search (pattern matching) algorithm in the world, and Boyer-Moore algorithm is one of those algorithm commonly used in finding long pattern in a longer string.
Probably, the most simple algorithm is called Naive Pattern Searching Algorithm:
- Match every character in the pattern and the corresponding position in the string. If all the characters match, return the resulting position.
- If there is a mismatch, simply move the pattern by 1 character.
- Repeat the process until the pattern hit the end of the algorithm. However, the algorithm is not efficient. In most of the case, the algorithm takes Θ(nm).
In Boyer-Moore algorithm, instead of comparing from the left to the right, it compares from the right to the left.
Then two rules apply when a mismatch happens:
- Bad character rule: If a mismatch happens on pattern position p and pattern's first character is at position**_ i **, the mismatched character is at **(p + i)_**. If the mismatched character appears on the left side of mismatched character, move the pattern so that the character are in the same position, and repeat the process of matching. If not, simply move the entire pattern by the length of pattern.
- Good suffix rule: If a mismatch happens, some continuous behind the mismatch (called suffix) appears in front of mismatch position (prefix), move so that the prefix and suffix part meet.
Boyer-Moore Algorithm is a simple combination of these two rules, and each step will move at least 1 step. If one rule skip more step, apply the rule.