ラビン・カープアルゴリズムとは？仕組みとC++実装例をわかりやすく解説

ラビン・カープ（Rabin-Karp）アルゴリズムは、テキストの中から特定のパターンを効率よく探し出すための文字列検索アルゴリズムの一つです。ナイーブな手法と同じく検索ウィンドウを1文字ずつずらしながら照合を行いますが、毎回すべての文字を比較するのではなく、まず各ウィンドウのハッシュ値を計算します。そして、ハッシュ値が一致した場合にのみ、文字単位の詳細な照合を実行します。この仕組みにより、無駄な文字比較を大幅に削減でき、検索処理が高速化されます。

平均的な時間計算量は O(m+n) ですが、ハッシュの衝突が多発するような最悪ケースでは O(mn) になる点に注意が必要です。

入力と出力

入力：
  対象文字列："ABAAABCDBBABCDDEBCABC"、パターン："ABC"

出力：
  パターンが見つかった位置: 4
  パターンが見つかった位置: 10
  パターンが見つかった位置: 18

アルゴリズム

rabinKarpSearch(text, pattern, prime)

入力： 検索対象のテキストとパターン、およびハッシュ値の計算に使用する素数。

出力： パターンが見つかった位置（該当箇所が複数ある場合はすべて）。

Begin
    patLen := パターンの長さ
    strLen := テキストの長さ
    patHash := 0、strHash := 0、h := 1
    maxChar := 文字セット内の総文字数

    pattern 内の各文字インデックス i について繰り返す
        h := (h * maxChar) mod prime
    done

    pattern の各文字インデックス i について繰り返す
        patHash := (maxChar * patHash + pattern[i]) mod prime
        strHash := (maxChar * strHash + text[i]) mod prime
    done

    for i := 0 to (strLen - patLen) まで繰り返す
        if patHash = strHash ならば
            for charIndex := 0 to patLen - 1 まで繰り返す
                if text[i+charIndex] ≠ pattern[charIndex] ならば
                    ループを抜ける
            done
            if charIndex = patLen ならば
                位置 i にパターンが見つかったことを出力する
        if i < (strLen - patLen) ならば
            strHash := (maxChar * (strHash - text[i] * h) + text[i+patLen]) mod prime
        if strHash < 0 ならば
            strHash := strHash + prime
    done
End

ローリングハッシュによる高速化のポイント

このアルゴリズムの鍵となっているのが「ローリングハッシュ」です。ウィンドウを1つずらすたびにハッシュを最初から計算し直すのではなく、「先頭の文字を取り除き、末尾に新しい文字を追加する」という操作で O(1) で更新できます。また、ハッシュ計算に素数を用いることで、異なる文字列が偶然同じハッシュ値を持つ衝突（誤検出）の発生確率を低く抑えています。ただし、衝突を完全に防ぐことはできないため、ハッシュ値が一致した場合には必ず文字列そのものの照合で確認します。

C++による実装例

#include<iostream>
#define MAXCHAR 256
using namespace std;

void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int charIndex, pattHash = 0, strHash = 0, h = 1;

    for(int i = 0; i<patLen-1; i++) {
        h = (h*MAXCHAR) % prime;      // h = {d^(M-1)} mod prime を計算
    }

    for(int i = 0; i<patLen; i++) {
        pattHash = (MAXCHAR*pattHash + pattern[i]) % prime;   // パターンのハッシュ値
        strHash = (MAXCHAR*strHash + mainString[i]) % prime;  // 先頭ウィンドウのハッシュ値
    }

    for(int i = 0; i<=(strLen-patLen); i++) {
        if(pattHash == strHash) {     // ハッシュ値が一致したら文字照合を行う
            for(charIndex = 0; charIndex < patLen; charIndex++) {
                if(mainString[i+charIndex] != pattern[charIndex])
                    break;
            }
            if(charIndex == patLen) { // パターンが見つかった
                (*index)++;
                array[(*index)] = i;
            }
        }

        if(i < (strLen-patLen)) {     // 次のウィンドウのハッシュ値を求める
            strHash = (MAXCHAR*(strHash - mainString[i]*h) + mainString[i+patLen])%prime;
            if(strHash < 0) {
                strHash += prime;     // ハッシュ値が負になった場合は正に補正する
            }
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int prime = 101;
    int index = -1;
    rabinKarpSearch(mainString, pattern, prime, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "パターンが見つかった位置: " << locArray[i] << endl;
    }
}

実行結果

パターンが見つかった位置: 4
パターンが見つかった位置: 10
パターンが見つかった位置: 18