What are the main differences between the Knuth-Morris-Pratt and Boyer-Moore search algorithms?

Question

What are the main differences between the Knuth-Morris-Pratt search algorithm and the Boyer-Moore search algorithm? What are the main differences in how they work?

Answer 1

Direction of Comparison:

KMP: Scans the pattern left-to-right

1. Compares characters from left to right in the pattern

Boyer-Moore: Scans the pattern right-to-left

1. Compares characters from right to left in the pattern

Preprocessing:

KMP: Builds a "failure function" or "prefix table"

1. Analyzes the pattern to find longest proper prefix that is also a suffix
2. Used to avoid re-comparing characters we already know match

Boyer-Moore: Uses two rules with lookup tables

1. Bad character rule: table of last occurrence of each character in pattern
2. Good suffix rule: table based on matching suffixes

Skip Logic:

KMP: Never moves backward in the text

1. When mismatch occurs, shifts pattern based on prefix table
2. Skips ahead but typically by smaller amounts
3. Guarantees each text character examined at most once

Boyer-Moore: Can skip large portions of text

1. Uses bad character rule to skip when text character not in pattern
2. Can skip multiple characters at once
3. More aggressive skipping, especially with large alphabets

Performance:

KMP:

1. Worst case: O(n + m) where n = text length, m = pattern length
2. Good for small alphabets
3. Simpler to implement

Boyer-Moore:

1. Worst case: O(nm) but rarely occurs
2. Average case: O(n/m) - sublinear, very fast in practice
3. Best for large alphabets and longer patterns
4. More complex to implement

Practical difference:

Boyer-Moore is generally faster in practice because it can skip more characters, especially when searching English text or DNA sequences. KMP has better worst-case guarantees and is simpler to understand and code.