ローリングハッシュにより文字列検索をO(m*n) => O(m+n)に高速化

参考

• 蟻本第二版 p332

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

用途

• 文字列検索の高速化

ナイーブな文字列検索 O(m*n)

• 普通に文字列検索を実装すると、
  • 文字列sから文字列tを探すとして
  • sの長さsl
  • tの長さtl
  • sのindex=0から滑らせてtの長さ分一致をチェックするので、計算量はO(sl * tl)
• ナイーブな実装↓

// s内のtを検索
vector<ll> naive_search(string s, string t){
    vector<ll> index_list;
    FOR(i, 0, s.size() - t.size() + 1){
        
        bool is_same = true;
        FOR(j, 0, t.size()){
            if(s[i+j]!=t[j]){
                is_same = false;
                break;
            }
        }
        if(is_same){
            index_list.push_back(i);
        }
    }
    return index_list;
}

ローリングハッシュを用いた文字列検索 O(m+n)

• 互いに素な定数 1<b<h を用意する
• 文字列 t のハッシュ値を以下で定義する

• sの先頭からtl分の部分文字列のハッシュを求める
  • 部分文字列を s[1...tl]と書くとする
• tのハッシュを求める
• ハッシュが一致すれば文字列も一致している
  • (ハッシュは衝突していないとする)
• 次はsの2文字目からtl分を使ってハッシュを求めたいが、これは先程求めたsの部分文字列のハッシュに少し足し引きすれば求まる
  • O(1)
  • 下記画像参考

• 詳しくは蟻本(第二版 p332)を見てほしい。hを2⁶⁴とし、型をunsigned long longとすることでmodを省略している

検証コード

// s内のtを検索
vector<ll> naive_search(string s, string t){
    vector<ll> index_list;
    FOR(i, 0, s.size() - t.size() + 1){
        
        bool is_same = true;
        FOR(j, 0, t.size()){
            if(s[i+j]!=t[j]){
                is_same = false;
                break;
            }
        }
        if(is_same){
            index_list.push_back(i);
        }
    }
    return index_list;
}

vector<ll> rolling_hash_search(string s, string t){
    vector<ll> index_list;
    ll SL = s.size();
    ll TL = t.size();

    // b, hは互いに素 (gcd == 1)
    ll b = 1e6 + 7;
    ll h = 1e9 + 7;

    // 蟻本でいう、bのm乗
    ll a = 1;
    FOR(i, 0, TL){
        a *= b;
        a %= h;
    }
    
    // 先頭のローリングハッシュ
    ll s_hash = 0;
    FOR(i, 0, TL){
        s_hash = s_hash * b + s[i];
        s_hash %= h;    
    }

    ll t_hash = 0;
    FOR(i, 0, TL){
        t_hash = t_hash * b + t[i];
        t_hash %= h;    
    }

    // sの始点を1つずつ進めながらハッシュ値をチェック
    FOR(i, 0, SL - TL + 1){
        if(s_hash==t_hash){
            index_list.push_back(i);
        }

        if(i+TL<SL){
            s_hash = s_hash * b - s[i] * a + s[i+TL];
            s_hash %= h;
        }
    }

    return index_list;
}

int main(){
    string s = "unvhusmjlvieloveuybouqvnqjygutqlovedkfsdfgheaiuloveaeiuvaygayfg";
    string t = "love";

    auto A = naive_search(s, t);
    vprint(A);

    auto B = rolling_hash_search(s, t);
    vprint(B);
    
    return 0;
}

出力

12 31 47 
12 31 47

注意点

• modをとるhが小さいと衝突しやすい
• 参考問題 https://yukicoder.me/submissions/338998

衝突

• ll b = 1e6 + 7; としていますが、最初はll b = 1e5 + 7; としていて、それだと
• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
• こちらでWAになるものがあったので修正した

ll b = 1e7 + 7;
ll h = 1e11 + 7;

• これも素数っぽくていいかも

h=2⁶⁴

• AOJが通らないので書き直した
• http://perogram.hateblo.jp/entry/2019/05/21/235639