C++1z 文字列検索アルゴリズム

C++

C++1zでは、文字列内の文字列を高速に検索するためのアルゴリズムとして、「ボイヤー・ムーア法 (Boyer-Moore)」と「ボイヤー・ムーア・ホースプール法 (Boyer-Moore-Horspool)」が導入されます。

これは、既存のstd::search()アルゴリズムを拡張する形で行われ、検索アルゴリズムを外部から指定するためのパラメータが追加されます。

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

int main()
{
    // ボイヤー・ムーア法で、文字列内の特定文字列を検索
    const std::string corpus = "…"; // 検索対象
    const std::string pattern = "…"; // 対象の中に見つけたい文字列

    auto it = std::search(
                corpus.begin(),
                corpus.end(),
                std::boyer_moore_searcher(
                    pattern.begin(),
                    pattern.end()
                ));
    if (it != corpus.end()) {
        std::cout << "found" << std::endl;
    }
    else {
        std::cout << "not found" << std::endl;
    }
}

検索アルゴリズムは以下の3つが用意されます。

  • default_searcher
  • boyer_moore_searcher
  • boyer_moore_horspool_searcher

default_searcherはこれまで通りのstd::search()の動作をします。

宣言

// <algorithm>
namespace std {
    template <class ForwardIterator, class Searcher>
    ForwardIterator search(ForwardIterator first, ForwardIterator last,
                           const Searcher& searcher);
}

// <functional>
namespace std {
    // 検索ポリシークラス
    template <class ForwardIterator, class BinaryPredicate = equal_to<>>
    class default_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_horspool_searcher;
}

Boostと標準の差異

Boost 1.50.0でBoost Algorithm Libraryがリリースされ、そこに文字列検索のアルゴリズムが含まれています。Boost 1.61.0現在は、std::search()を拡張するようなポリシーベースの設計ではなく、アルゴリズムごとに別名の関数が定義されています。

Boostの方には、標準に追加される2つのアルゴリズムに加えて、knuth_morris_pratt_search()アルゴリズムがあります。これはKMP法という名前で知られているアルゴリズムです。(クヌース・モリス・プラット法)

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。