5. operator()

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

履歴 編集

function template
<functional>

std::boyer_moore_horspool_searcher::operator()(C++17)

template <class RandomAccessIterator2>
std::pair<RandomAccessIterator2, RandomAccessIterator2>
  operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;

概要

検索を実行する。

この関数は、全体のシーケンス範囲[first, last)に含まれる部分シーケンス範囲[pat_first, pat_last)を検索する。検索対象 (pattern) となる部分シーケンスは、このクラスのコンストラクタで登録し、メンバ変数として保持されている。

この関数の戻り値としては、見つかった部分シーケンスの、全体シーケンス上のイテレータ範囲が返る。

効果

シーケンス内の部分シーケンスと等値になる範囲を検索する。

戻り値

  • 部分シーケンス[pat_first, pat_last)が空である場合、make_pair(first, first)を返す
  • イテレータiとjとして以下を定義し、
    • i : イテレータ範囲[first, last)のうち、部分範囲[pat_first, pat_last)が現れる最初の位置を指すイテレータ。各要素の等値比較は、pred(*(i + n), *(pat_first + n)) != falseで判定する
    • j : next(i, distance(pat_first, pat_last))
    • 合致する部分シーケンスが見つかった場合、make_pair(i, j)を返す
  • 合致する部分シーケンスが見つからなかった場合、make_pair(last, last)を返す

計算量

最大で(last - first) * (pat_last - pat_first)回だけ述語を適用する

例

#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

処理系

参照