Algoogle

Algorithm for Programming Contest

Rolling-Hash法(Rabin-Karp法)

基本情報


計算量  
構築
空間

N := 文字列の長さ

解説


文字列からハッシュを生成しておくことでその部分文字列同士の比較をO(1)でできるようにする.
2つの素数でmodをとるものと2^64でmodをとるものの2つを用意した.
2^64でmodをとるのは容易にハッシュ衝突を起こす上, そのようなケースを簡単に作れるのでお勧めできない).
10^9程度の素数でmodをとってもハッシュ衝突をすぐに起こすので複数の素数を使うことにした.

ハッシュの衝突に関してはハッシュを衝突させる話が参考になる.

コード


(rolling-hash.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int MAX = 500000, MS = 2;
const long long mod[] = {999999937LL, 1000000007LL}, base = 9973;
struct rolling_hash {
    int n;
    vector<long long> hs[MS], pw[MS];
    rolling_hash(){}
    rolling_hash(const string &s) {
        n = s.size();
        for (int i = 0; i < MS; i++) {
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            for (int j = 0; j < n; j++) {
                pw[i][j+1] = pw[i][j]*base%mod[i];
                hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
            }
        }
    }

    long long hash(int l, int r, int i) { return ((hs[i][r]-hs[i][l]*pw[i][r-l])%mod[i]+mod[i])%mod[i]; }

    bool match(int l1, int r1, int l2, int r2) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l1,r1,i)==hash(l2,r2,i);
        return ret;
    }

    bool match(int l, int r, long long h[]) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l,r,i)==h[i];
        return ret;
    }
};

struct rolling_hash64 {
    int n;
    vector<long long> hs, pw;
    rolling_hash64(){}
    rolling_hash64(const string &s) {
        n = s.size();
        hs.assign(n+1,0);
        pw.assign(n+1,0);
        pw[0] = 1;
        for (int i = 0; i < n; i++) {
            hs[i+1] = hs[i]*base+s[i];
            pw[i+1] = pw[i]*base;
        }
    }

    long long hash(int l, int r) { return hs[r]-hs[l]*pw[r-l]; }
    bool match(int l1, int r1, int l2, int r2) { return hash(l1,r1) == hash(l2,r2); }
};

問題


Comments