Rolling Hash

概要

連続部分列の hash を O(1) で取得可能なデータ構造。

作成part

Hash関数

• 基数 と 法 を定めて、法の下で 基数の累乗を線形結合的にしてhashを得る。
• N ≦ 10^5 なら、基数を 2^61 - 1 にしてる為、hash衝突がほとんど起こらない。( sqrt(基数) くらいだと 50% 位衝突 )

法 と 基数

• 法は 2^61 - 1 固定。( 2進数の剰余は bit shift & フェルマーの小定理 により、剰余が高速に計算可能な為。 )
• 基数は 乱択。ただ 文字列を扱う際は 128 以上、数列を扱う場合は最大値以上 を取る必要あり。( 線形性を利用しており、基数の累乗が他の累乗に影響を与えないようにする為 )
• また基数は 原子根 にするとより衝突が起こりにくい。
  Rolling Hashで基数に原始根を使う【新歓ブログリレー2020 36日目】

  この記事は新歓ブログリレー2020 37日目の記事です。 こんにちは。algorithm班のidatenです。普段は、競技プログラミングをしています。今回は、競技プログラミングで使う際に、Rolling Hashというアルゴリズムの衝突の話と、基数にランダムな原始根を使ってみるという話をしようと思います。 Rolling Hashとは 文字列(もしくは数列)をHash値に変換することで、文字列同士の比較をO(1) ですることができるようになります。これによって、文字列の検索や比較が高速に行うことができます。 詳しくは、蟻本p.332かラビンカープ法のおはなし+二次元のロリハいいぞ [https://trap.jp/post/900/]の1,2,3章を参照してください。 Hashの衝突 以下ではRolling Hashで使う素数をp、基数をbとします。 Hash値を用いて文字列を比較する場合、「Hash値が等しいならば、下の文字列も等しい」という前提を置いていますが、実際は成り立ちません。異なる文字列であるが、同じHash値となってしまうことをHashの衝突といいます。 しかし

  

  trap.jp
  
  judge.u-aizu.ac.jp
  

method

• mulMod(x ,y) : 積の剰余を取得する関数。( __int128_t に対して % は遅い為作成する )
• get(l,r) : インスタンス作成時の文字列の [l,r) の部分列の hash を求める関数。(累積和的に hash が求まる)

Program

using ull = unsigned long long;
vector<ull> powr; // 基数の累乗

class RollingHash {
    public:
    RollingHash(const string &s){
        if(base == 0){
            // base を 2^61-1の原始根 & 1e9以上 で初期化
            random_device rnd;
            mt19937 mt(rnd());
            uniform_int_distribution<ull> rand(1,INT_MAX);
            while(1){
                ull k = rand(mt);
                base = modPow(37,k);
                if(euclid(Mod-1,k) == 1 && base > 1e9)break;
            }
        }
        powr.assign(1,1);
        int size = s.size();
        hash.assign(size+1,0);
        // 左端~の hash 前計算
        for(int i=0; i<size; i++){
            hash[i+1] = mulMod(hash[i],base) + s[i];
            hash[i+1] = getMod(hash[i+1]);
        }
    }

    ull get(int l, int r){
        ull res = hash[r] - mulMod(hash[l],getPow(r-l));
        return getMod(res + Positivizer);
    }

    private:
    static const ull Mod = (1LL << 61) - 1;
    static const ull Positivizer = Mod * 7;
    static ull base;  // 基数
    vector<ull> hash; // hash の cash

    static ull getPow(int n){
        while(powr.size() <= n){
            // 次の基数の累乗を求める
            powr.push_back(mulMod(powr.back(), base));
        }
        return powr[n];
    }

    static ull mulMod(ull x,ull y){
        // Fermatの小定理 & 2進数のmod を利用
        __int128_t t = (__int128_t) x*y;
        t = (t >> 61) + (t & Mod);
        if(t >= Mod)t -= Mod;
        return (ull)t;
    }

    static ull getMod(ull val){
        val = (val >> 61) + (val & Mod);
        if(val >= Mod)val -= Mod;
        return (ull)val;
    }

    static ull euclid(ull a,ull b){
        if(b != 0)return euclid(b,a%b);
        else return a;
    }

    static ull modPow(ull a, ull b) {
        ll res= 1;
        for(; b; a=getMod(a*a), b>>=1) {
            if(b & 1)res = getMod(res*a);
        }
        return res;
    }
};
ull RollingHash::base;