Rolling Hash
(lib/string/rolling_hash.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/string/rolling_hash.hpp"

Rolling Hash

使い方

• RollingHash(s, base): 文字列 s について、基数を base としたハッシュテーブルを構築します。
• get(l, r): [l, r) のハッシュ値を取得します。
• connect(h1, h2, h2len): ハッシュ値 h1 と長さ h2len のハッシュ値 h2 を結合します。
• LCP(b, l1, r1, l2, r2): 区間 [l1, r1) と ハッシュテーブルが b となる区間 [l2, r2) の文字列の最長接頭辞を求めます。

計算量

• RollingHash(s, base): $\mathrm{O}(\lvert S\lvert)$
• get(l, r): $\mathrm{O}(1)$
• connect(h1, h2, h2len): $\mathrm{O}(1)$
• LCP(b, l1, r1, l2, r2): $\mathrm{O}(\log \lvert S\lvert)$

Verified with

• test/aoj/alds1/alds1_14_b.test.cpp

Code

#pragma once

/**
 * @brief Rolling Hash
 * @docs docs/string/rolling_hash.md
 */

struct RollingHash{
    vector<unsigned long long> hashed, power;
    const unsigned long long mod = (1uLL << 61) - 1;

    unsigned long long mul(unsigned long long a, unsigned long long b) const {
        long long ret = a * b - mod * (unsigned long long)(1.0L / mod * a * b);
        return ret + mod * (ret < 0) - mod * (ret >= (long long) mod);
    }

    RollingHash(const string &s, unsigned base = 10007){
        int siz = (int) s.size();
        hashed.assign(siz + 1, 0);
        power.assign(siz + 1, 0);
        power[0] = 1;
        for(int i = 0; i < siz; i++){
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
        }
    }

    // [l, r)
    unsigned long long get(int l, int r) const {
        unsigned long long ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
        if(ret >= mod) ret -= mod;
        return ret;
    }

    unsigned long long connect(unsigned long long h1, unsigned long long h2, int h2len) const {
        unsigned long long ret = mul(h1, power[h2len]) + h2;
        if(ret >= mod) ret -= mod;
        return ret;
    }

    int LCP(const RollingHash &b, int l1, int r1, int l2, int r2){
        int len = min(r1 - l1, r2 - l2);
        int low = -1, high = len + 1;
        while(high - low > 1){
            int mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};

#line 2 "lib/string/rolling_hash.hpp"

/**
 * @brief Rolling Hash
 * @docs docs/string/rolling_hash.md
 */

struct RollingHash{
    vector<unsigned long long> hashed, power;
    const unsigned long long mod = (1uLL << 61) - 1;

    unsigned long long mul(unsigned long long a, unsigned long long b) const {
        long long ret = a * b - mod * (unsigned long long)(1.0L / mod * a * b);
        return ret + mod * (ret < 0) - mod * (ret >= (long long) mod);
    }

    RollingHash(const string &s, unsigned base = 10007){
        int siz = (int) s.size();
        hashed.assign(siz + 1, 0);
        power.assign(siz + 1, 0);
        power[0] = 1;
        for(int i = 0; i < siz; i++){
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
        }
    }

    // [l, r)
    unsigned long long get(int l, int r) const {
        unsigned long long ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
        if(ret >= mod) ret -= mod;
        return ret;
    }

    unsigned long long connect(unsigned long long h1, unsigned long long h2, int h2len) const {
        unsigned long long ret = mul(h1, power[h2len]) + h2;
        if(ret >= mod) ret -= mod;
        return ret;
    }

    int LCP(const RollingHash &b, int l1, int r1, int l2, int r2){
        int len = min(r1 - l1, r2 - l2);
        int low = -1, high = len + 1;
        while(high - low > 1){
            int mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};

Back to top page