最終更新日時(UTC): 2025年07月08日 15時33分39秒
Akira Takahashi が更新

履歴 編集

class template
<functional>

# std::boyer_moore_horspool_searcher(C++17)

    namespace std {
      template <class RandomAccessIterator1,
                class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
                class BinaryPredicate = equal_to<>>
      class boyer_moore_horspool_searcher;
    }

## 概要

`std::boyer_moore_horspool_searcher`は、ボイヤー・ムーア・ホースプール法によって、シーケンス (text) からサブシーケンス (pattern) を検索する関数オブジェクトである。

このクラスは、コンストラクタおよびクラステンプレートのテンプレート引数で、検索対象となるサブシーケンス (pattern) を登録し、関数呼び出し演算子で全体のシーケンス (text) を指定して検索を実行する。

このアルゴリズムは本来、文字列から部分文字列を高速に検索するためのアルゴリズムであるが、仕様として対象を文字列に限定してはいない。

ボイヤー・ムーア・ホースプール法は、ボイヤー・ムーア法 (`std::boyer_moore_searcher`) を簡略化したアルゴリズムである。ボイヤー・ムーア法よりも、初期化とループごとの処理で少しだけオーバーヘッドが少ないが、最良ケースでのビッグオー記法での計算量は、どちらも同じとなる。最悪計算量はボイヤー・ムーア法よりも高くなるため、入力データによって性能が変わる。

## 要件

- `RandomAccessIterator1`が指す値型は、デフォルト構築可能、コピー構築可能、コピー代入可能の要件を満たすこと

## 備考

- このクラステンプレートは複数のテンプレート引数をもつが、それを容易に使用するためのヘルパ関数 (`make_boyer_moore_horspool_searcher()`) は定義されていない。これは、C++17で導入されたクラステンプレートパラメータの推論機能と併用することを意図したものである
- このクラスは`std::search()`アルゴリズムと併用することを意図して設計されているが、このクラス単体で使用できる

## メンバ関数

名前 | 説明 | 対応バージョン
--- | --- | ---
`(constructor)` | コンストラクタ | C++17
`operator()` | 検索を実行する | C++17

## 例

    #include <iostream>
    #include <string>
    #include <functional>
    #include <iterator>

    int main()
    {
      // text内のpatternを検索する
      //                      xxxx
      std::string text = "babcabaabaac";
      std::string pattern = "abaa";

      // patternを登録
      std::boyer_moore_horspool_searcher searcher {
        pattern.cbegin(),
        pattern.cend()
      };

      // textを指定して検索を実行
      using iterator = std::string::const_iterator;
      std::pair<iterator, iterator> result = searcher(text.cbegin(), text.cend());

      // 見つかった
      if (result.first != result.second) {
        // 見つかった位置を取得
        std::ptrdiff_t n = std::distance(text.cbegin(), result.first);

        // 見つかった文字列 (pattern) を取得
        std::string s {result.first, result.second};

        std::cout << n << std::endl;
        std::cout << s << std::endl;
      }
      // 見つからなかった
      else {
        std::cout << "not found" << std::endl;
      }
    }

### 出力

    4
    abaa

## バージョン

### 言語

- C++17

### 処理系

- Clang:
- GCC: 7.3 ✅
- Visual C++: ??

## 参照

- N3905 Extending `std::search` to use Additional Searching Algorithms (Version 4)
- P0220R1 Adopt Library Fundamentals V1 TS Components for C++17 (R1)
- P0253R1 Fixing a design mistake in the searchers interface in Library Fundamentals