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法)