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
) を簡略化したアルゴリズムである。ボイヤー・ムーア法よりも、初期化とループごとの処理で少しだけオーバーヘッドが少ないが、最良ケースでのビッグオー記法での計算量は、どちらも同じとなる。最悪計算量はボイヤー・ムーア法よりも高くなるため、入力データによって性能が変わる。
要件
備考
- このクラステンプレートは複数のテンプレート引数をもつが、それを容易に使用するためのヘルパ関数 (
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++: ??