【C++17】boyer_moore_searcherで高速な文字列検索を行う方法

2025年9月10日

はじめに

C++で、長い文字列の中から特定のパターン（部分文字列）を探し出す場合、標準ライブラリ<algorithm>のstd::search関数が利用できます。

C++17では、このsearch関数と組み合わせて使うための検索オブジェクト（searcher）が導入されました。これにより、従来よりもはるかに高速な文字列検索アルゴリズム（ボイヤー・ムーア法やボイヤー・ムーア・ホースプール法）を、標準ライブラリの機能だけで簡単に利用できるようになりました。

この記事では、std::boyer_moore_searcherを使って、文字列を高速に検索する方法を解説します。

【前提】C++17とは？

C++17は、2017年に正式化されたC++言語の規格です。検索オブジェクトはこのC++17で導入されたため、利用するにはC++17に対応したコンパイラが必要です。

`boyer_moore_searcher` を使ったサンプルコード

このコードは、長いテキストの中から、"fox"という単語をboyer_moore_searcherを使って検索し、見つかった位置を出力します。

完成コード

#include <iostream>
#include <string>
#include <algorithm>   // std::search
#include <functional>  // std::boyer_moore_searcher

using namespace std;

int main() {
    string text_to_search = "The quick brown fox jumps over the lazy dog.";
    string pattern_to_find = "fox";

    // 1. 検索パターンから、ボイヤー・ムーア法の検索オブジェクトを作成
    auto searcher = boyer_moore_searcher(
        pattern_to_find.begin(),
        pattern_to_find.end()
    );

    // 2. std::searchに、検索対象、検索パターン(searcher)、を渡す
    auto result_iterator = search(
        text_to_search.begin(),
        text_to_search.end(),
        searcher
    );
    
    // 3. 結果を判定
    if (result_iterator != text_to_search.end()) {
        // distanceで、先頭から見つかった位置までの距離（インデックス）を計算
        auto position = distance(text_to_search.begin(), result_iterator);
        cout << "文字列「" << pattern_to_find << "」が見つかりました。" << endl;
        cout << "位置: " << position << endl;
    } else {
        cout << "文字列が見つかりませんでした。" << endl;
    }

    return 0;
}

コードの解説

ボイヤー・ムーア法とは？

ボイヤー・ムーア法（およびその派生であるボイヤー・ムーア・ホースプール法）は、文字列検索アルゴリズムの一つです。検索パターンを末尾から比較し、不一致だった場合に、その文字の情報を使って**大きくジャンプ（スキップ）**することで、先頭から一文字ずつ比較する単純なアルゴリズムよりも、大幅に高速な検索を実現します。

1. `boyer_moore_searcher(...)`

<functional>ヘッダーで提供されます。
引数として渡された検索パターン（この場合は"fox"）を、内部的に解析して、高速な検索に必要な情報を事前計算します。
この事前計算の結果を保持した「検索オブジェクト」を返します。

2. `std::search(..., searcher)`

<algorithm>ヘッダーで提供されます。
C++17で、第3引数に検索オブジェクトを受け取るオーバーロードが追加されました。
このsearch関数は、与えられた検索オブジェクトが持つアルゴリズム（この場合はボイヤー・ムーア法）を使って、text_to_searchの中からパターンを探します。

3. 結果の解釈

search関数は、パターンが見つかった場合はその開始位置を指すイテレータを、見つからなかった場合は検索範囲の終端イテレータを返します。std::distance関数を使うことで、コンテナの先頭から、見つかった位置までのインデックス番号を計算できます。

まとめ

今回は、C++17の検索オブジェクトを使って、高速な文字列検索を行う方法を解説しました。

std::boyer_moore_searcher (または std::boyer_moore_horspool_searcher) で、検索パターンから検索オブジェクトを作成する。
std::search アルゴリズムに、検索対象の範囲と、作成した検索オブジェクトを渡す。

これにより、自前で複雑なアルゴリズムを実装することなく、標準ライブラリだけで、非常に効率的な文字列検索を簡単に行うことができます。

よかったらシェアしてね！