Search Algorithms

Boyer-Moore vs Boyer-Moore-Horspool Search Algorithms

What are the differences and benefits of using std::boyer_moore_searcher versus std::boyer_moore_horspool_searcher in practical scenarios?

Abstract art representing computer programming

Boyer-Moore and Boyer-Moore-Horspool are two efficient search algorithms provided by the C++ standard library.

Both are designed for substring searches and can be significantly faster than a simple linear search, especially for large texts.

Boyer-Moore Search Algorithm

The Boyer-Moore algorithm is known for its efficiency in practice. It preprocesses the pattern to create two tables that are used to skip sections of the text, making the search faster.

Benefits:

  • Fast for Large Patterns: It can skip large sections of text, making it efficient for long patterns.
  • Good Average Performance: Generally performs well across various types of text and patterns.

The following example shows how we can use std::boyer_moore_searcher:

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>

int main() {
  std::string text = "Lorem ipsum dolor sit"
    " amet, consectetur adipiscing elit.";
  std::string pattern = "dolor";

  std::boyer_moore_searcher searcher(
    pattern.begin(), pattern.end());
  auto result = std::search(
    text.begin(), text.end(), searcher);

  if (result != text.end()) {
    std::cout << "Pattern found at position "
      << std::distance(text.begin(), result);
  } else {
    std::cout << "Pattern not found";
  }
}
Pattern found at position 12

Boyer-Moore-Horspool Search Algorithm

The Boyer-Moore-Horspool algorithm is a simplified version of the Boyer-Moore algorithm. It only uses one table for preprocessing, which makes it simpler and sometimes faster for certain types of input.

Benefits:

  • Simpler Implementation: Easier to understand and implement compared to Boyer-Moore.
  • Faster for Short Patterns: Can be faster when the pattern is relatively short.

The following example shows how we can use std::boyer_moore_horspool_searcher:

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>

int main() {
  std::string text = "Lorem ipsum dolor sit amet,"
    " consectetur adipiscing elit.";
  std::string pattern = "dolor";

  std::boyer_moore_horspool_searcher searcher(
    pattern.begin(), pattern.end());
  auto result = std::search(
    text.begin(), text.end(), searcher);

  if (result != text.end()) {
    std::cout << "Pattern found at position "
      << std::distance(text.begin(), result);
  } else {
    std::cout << "Pattern not found";
  }
}
Pattern found at position 12

Key Differences

  • Preprocessing: Boyer-Moore uses two tables (bad character and good suffix) for preprocessing, while Boyer-Moore-Horspool uses only the bad character table.
  • Performance: Boyer-Moore can be faster for longer patterns and more complex texts due to its more sophisticated skipping mechanism. Boyer-Moore-Horspool might be faster for shorter patterns.

Choosing Between the Two

  • Use Boyer-Moore: When dealing with longer patterns or when the search performance is critical across varied text data.
  • Use Boyer-Moore-Horspool: For simpler and shorter patterns, where its simplicity and speed can be advantageous.

In summary, both algorithms are powerful tools for efficient substring searches. Your choice between them should depend on the specific requirements of your text data and pattern length.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved