4. boyer_moore_searcher

最終更新日時(UTC):
が更新

履歴 編集

class template
<functional>

std::boyer_moore_searcher(C++17)

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

概要

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

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

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

ボイヤー・ムーア法は、その簡略版であるボイヤー・ムーア・ホースプール法 (std::boyer_moore_horspool_searcher) に比べて、メモリ使用量が多い代わりに性能がよい。

要件

備考

  • このクラステンプレートは複数のテンプレート引数をもつが、それを容易に使用するためのヘルパ関数 (make_boyer_moore_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_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

処理系

参照