C++でローリングハッシュを実装する方法｜Rabin-Karp法による文字列検索を解説

ローリングハッシュとは

ローリングハッシュ（転がりハッシュ）とは、入力データ上を移動するウィンドウ（窓）ごとにハッシュ値を計算できるハッシュ関数のことです。ウィンドウが1文字分ずれたときも、ハッシュ全体を最初から計算し直すのではなく、前回の値から効率よく更新できる点が最大の特徴です。

Rabin-Karp法との関係

ローリングハッシュの最も有名な応用例が、Rabin-Karp（ラビン・カープ）文字列検索アルゴリズムです。RabinとKarpが提案したローリングハッシュ関数は整数値を計算し、文字列に対しては「その文字列を数値として表現した値」を返します。

Rabin–Karp法の解説では、乗算と加算だけで計算できる、次のような非常にシンプルなローリングハッシュ関数がよく使われます。

H = c1ak−1 + c2ak−2 + … + cka0

ここで、a は定数（基数）、c₁, c₂, …, c_k は入力文字を表します。H は文字数が増えると膨大な値になるため、扱える範囲に収めるために mod n（剰余演算）を適用します。

アルゴリズムの流れ

1. 定数 P_B = 227（基数）、P_M = 1000005（法）を定義する。
2. hash() 関数を定義する。
   ・文字列 s を引数として受け取る。
   ・整数 r を 0 で初期化する。
   ・各文字について r = r * P_B + s[i] を計算し、r %= P_M を適用する。
   ・r を返す。
3. rabin_karp(パターン n, 対象文字列 hstack) 関数を定義する。
   ・h1 = hash(n) としてパターンのハッシュ値を求める。
   ・h2 = 0、power = 1 で初期化する。
   ・パターンの長さ分だけ power = (power * P_B) % P_M を繰り返す。
   ・対象文字列を先頭から走査する。
     - h2 = h2 * P_B + hstack[i] として新しい文字を追加し、h2 %= P_M を適用する。
     - ウィンドウがパターンより長くなったら、先頭の文字の寄与を h2 から差し引く。
       結果が負になった場合は P_M を足して調整する。
     - ウィンドウの長さがパターンと一致し、かつ h1 == h2 なら開始位置を返す。
   ・最後まで見つからなければ -1 を返す。
4. 検索対象の文字列 s1 と、探したい文字列 s2 を入力として受け取る。
5. rabin_karp(s2, s1) の結果が -1 なら「見つからない」と表示し、
   それ以外なら見つかった位置を出力する。

C++による実装例

#include <iostream>
#include <string>
using namespace std;

const int P_B = 227;      // 基数
const int P_M = 1000005;  // 法（剰余を取る値）

// 文字列のハッシュ値を計算する
int hash(const string& s) {
    int r = 0;
    for (int i = 0; i < s.size(); i++) {
        r = r * P_B + s[i];
        r %= P_M;
    }
    return r;
}

// Rabin-Karp法による文字列検索
int rabin_karp(const string& n, const string& hstack) {
    int h1 = hash(n);   // パターンのハッシュ値
    int h2 = 0;         // 現在のウィンドウのハッシュ値
    int power = 1;

    // 基数の（パターン長）乗をあらかじめ計算しておく
    for (int i = 0; i < n.size(); i++)
        power = (power * P_B) % P_M;

    for (int i = 0; i < hstack.size(); i++) {
        // ウィンドウの末尾に新しい文字を追加
        h2 = h2 * P_B + hstack[i];
        h2 %= P_M;

        // ウィンドウがパターンより長い場合、先頭の文字を取り除く
        if (i >= n.size()) {
            h2 -= power * hstack[i - n.size()] % P_M;
            if (h2 < 0)
                h2 += P_M;
        }

        // パターンと同じ長さになり、ハッシュ値が一致したら位置を返す
        if (i >= n.size() - 1 && h1 == h2)
            return i - (n.size() - 1);
    }
    return -1;
}

int main() {
    string s1, s2;
    cout << "入力文字列を入力してください: ";
    getline(cin, s1);
    cout << "検索する文字列を入力してください: ";
    cin >> s2;

    int pos = rabin_karp(s2, s1);
    if (pos == -1)
        cout << "文字列は見つかりませんでした" << endl;
    else
        cout << "文字列 \"" << s2 << "\" は位置 " << pos << " で見つかりました" << endl;
    return 0;
}

実行結果

入力文字列を入力してください: Tutorialspoint
検索する文字列を入力してください: a
文字列 "a" は位置 6 で見つかりました

入力文字列を入力してください: Tutorialspoint
検索する文字列を入力してください: b
文字列は見つかりませんでした

計算量と実装上のポイント

このアルゴリズムの平均計算量は O(n + m)（n は対象文字列の長さ、m はパターンの長さ）と高速ですが、ハッシュ値の衝突が多発する最悪ケースでは O(n × m) まで悪化する可能性があります。実務で使う場合は、ハッシュ値が一致したときに実際の文字列比較を行って確認すると、より安全です。

また、法 P_M には大きな素数を選ぶとハッシュ値の偏りが減り、衝突の発生を抑えられます。剰余演算を毎ステップで行うのは、整数オーバーフローを防ぎながら計算を一定の範囲に保つための重要な工夫です。