Data Structures and Algorithms
Which is a characteristic of the Boyer-Moore algorithm for finding a pattern in a string?
- AIt compares the pattern starting from its last character and uses information such as the mismatched text character not appearing in the pattern to shift the pattern a long way at once
- BIt shifts the pattern one character at a time from the start of the text and compares every character of the pattern from first to last each time
- CIt sorts both the text and the pattern and then finds the pattern by binary search
Show answer and explanation
Answer: A. It compares the pattern starting from its last character and uses information such as the mismatched text character not appearing in the pattern to shift the pattern a long way at once
The Boyer-Moore algorithm compares the pattern from its last character and precomputes tables so that, for example, if the mismatched text character does not appear in the pattern at all, the whole pattern can be shifted past it. As a result, on natural-language text it can skip many characters without comparing them. With a text of length n and a pattern of length m, the naive method that shifts one character at a time and compares everything takes O(nm) in the worst case. The KMP algorithm also uses mismatch information to shift, but it compares from the start of the pattern and guarantees O(n + m) even in the worst case.
- A. Correct. Comparing from the end and making large shifts based on the mismatched character is the Boyer-Moore algorithm.
- B. This is the naive (brute-force) method, which takes O(nm) in the worst case.
- C. The task is to find positions within the string, and sorting would destroy the position information.