読者です 読者をやめる 読者になる 読者になる

Boost.Algorithm 検索アルゴリズム

C++

Boost.Algorithmには、以下の3つの検索アルゴリズムが用意されています:

  • boost::algorithm::boyer_moore_search() : BM法(Boyer-Moore)
  • boost::algorithm::boyer_moore_horspool_search() : BMH法(Boyer-Moore-Horspool)
  • boost::algorithm::knuth_morris_pratt() : KMP法(Knuth-Morris-Pratt)


どれも使い方は同じなので、ここではBM法だけ紹介します。以下がサンプルです:

#include <iostream>
#include <string>
#include <boost/algorithm/searching/boyer_moore.hpp>

int main()
{
    std::string text = "the stick, and made believe to worry it: then Alice dodged behind a";
    std::string pattern = "behind";

    // BM法で文字列検索
    decltype(text)::const_iterator it =
        boost::algorithm::boyer_moore_search(text.begin(), text.end(),
                                             pattern.begin(), pattern.end());

    if (it != text.end()) std::cout << "found" << std::endl;
    else                  std::cout << "not found" << std::endl;
}
found

text変数に入っている文字列から、"behind"という単語を検索しています。
検索アルゴリズムの引数は、対象文字列の範囲と、パターン文字列の範囲です。


ちなみにRange版の実装もあるのですが、コンパイルエラーになったのでパッチを送っておきました。
#7104 compile error boyer_moore_seach


参照:
Boyer-Morre Search - Boost Algorithm Library
Boyer-Moore-Horspool Search - Boost Algorithm Library
Knuth-Morris-Pratt Search - Boost Algorithm Library
文字列検索(BM法)
文字列検索(直感的な文字列検索とKMP法)