ラビン-カープアルゴリズムをC++で実装する

algorithmc++

ラビン-カープアルゴリズムはローリングハッシュを用いて部分文字列を探索するアルゴリズム。 ローリングハッシュというのは前のハッシュから先頭の要素を取り除き、次の要素を追加することによってO(1)で次のハッシュが得られるもの。

class rolling_hash {
    string str;
    int window_length = 0;
    long hash = 0;
    int head_idx = 0;
    long tail_pow;
    const int base = 128;
public:
    rolling_hash(string str, int window_length) {
        this->str = str;
        this->window_length = window_length;
        long pow = 1;
        for (int i = 0; i < window_length; i++) {
            hash += str[i] * pow;
            pow *= base;
        }
        tail_pow = pow / base;
    }
    int get() {
        return hash;
    }
    //    a_0 * base^0 + a_1 * base^1 + ... + a_n * base^n
    // =>                a_1 * base^0 + ... + a_n * base^n-1 + a_n+1 & base^n
    void roll() {
        head_idx++;
        hash -= str[head_idx-1];
        hash /= base;
        int tail_idx = head_idx+window_length-1;
        if (tail_idx >= str.length()) throw new out_of_range("the window is out of range");
        hash += str[tail_idx] * tail_pow;
    }
};

このハッシュが一致する部分を探索していく。ハッシュは衝突する可能性があるので一致した後に文字列比較を行う必要がある。

int index_of(string str, string substr) {
    int pattern = rolling_hash(substr);
    for (int i = 0; i < str.length(); i++) {
        string window = str.substr(i, substr.length());
        if (rolling_hash(window) == pattern) {
            if (window == substr) return i;
        }
    }
    return -1;
}

全体の文字列の長さをn、部分文字列の長さをmとすると、平均としてはO(n+m)で探すことができるが、全てのハッシュが衝突する最悪の場合は毎回文字列比較を行うことになるので総当たりと同じO(nm)となってしまう。ただ、複数の部分文字列を探索する場合に実行時間がその数に依存しない特長があり、盗用の検出などに使われる。

参考

Rabin–Karp algorithm - Wikipedia

プログラミングコンテストチャレンジブック [第2版]