string/rollinghash.hpp

• View this file on GitHub
• Last update: 2025-05-09 08:57:16+00:00
• Include: #include "string/rollinghash.hpp"

Depends on

• math/modint230.hpp

Code

#pragma once
#include "modint230"
#include <bits/stdc++.h>
using namespace std;
template <typename T = char>
struct RollingHash {
    mint230 generate_base() {
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<uint64_t> rand(1, mint230::mod() - 1);
        return mint230(rand(mt));
    }
    mint230 base, base_inv;
    vector<mint230> bases, base_invs;
    vector<T> pre, suf;
    vector<mint230> PRE{mint230(0)}, SUF{mint230(0)};
    void expand_bases(size_t n) {
        if (bases.size() < n+1) {
            int pre_sz = (int)bases.size();
            bases.resize(n + 1);
            for (int i=pre_sz-1; i<n; i++) {
                bases[i+1] = bases[i] * base;
            }
        }
    }
    void expand_base_invs(size_t n) {
        if (base_invs.size() < n+1) {
            int pre_sz = (int)base_invs.size();
            base_invs.resize(n+1);
            for (int i=pre_sz-1; i<n; i++) {
                base_invs[i+1] = base_invs[i] * base_inv;
            }
        }
    }
    RollingHash(const string& s) {
        for (auto& c : s) push_back(c);
    }
    RollingHash(const vector<T>& s) {
        for (auto& c : s) push_back(c);
    }
    int size() { return (int)pre.size() + (int)suf.size(); }
    void push_front(T c) {
        expand_base_invs(pre.size()+1);
        PRE.push_back(PRE.back() + base_invs[pre.size()+1] * mint230(c));
        pre.push_back(c);
    }
    void push_back(T c) {
        expand_bases(suf.size());
        SUF.push_back(SUF.back() + bases[suf.size()] * mint230(c));
        suf.push_back(c);
    }
    T operator[](int k) {
        assert(0<=k && k<size());
        k -= pre.size();
        return (k < 0 ? pre[~k] : suf[k]);
    }
    mint230 get(int r) {
        assert(0<=r && r<=size());
        r -= (int)pre.size();
        expand_bases(pre.size());
        if (r < 0) {
            return bases[pre.size()] * (PRE.back() - PRE[-r]);
        } else {
            return bases[pre.size()] * (PRE.back() + SUF[r]);
        }
    }
    mint230 get(int l, int r) {
        assert(0 <= l and l <= r and r <= size());
        expand_base_invs(l);
        return base_invs[l] * (get(r) - get(l));
    }
    int lcp(const RollingHash& b) {
        int len = min(size(), b.size());
        int low = 0, high = len + 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (get(mid) == b.get(mid)){
                low = mid;
            }
            else {
                high = mid;
            }
        }
        return low;
    }
    int lcp(const RollingHash& b, int l1, int l2) {
        assert(l1 <= size());
        assert(l2 <= b.size());
        int len = min(size() - l1, b.size() - l2);
        int low = 0, 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;
    }
    mint230 combine(mint230 h1, int h1_len, mint230 h2) {
        expand_bases(h1_len);
        return h1 + h2 * bases[h1_len];
    }
    void clear() {
        pre.clear();
        pre.shrink_to_fit();
        suf.clear();
        suf.shrink_to_fit();
        PRE = {mint230(1)};
        PRE.shrink_to_fit();
        SUF = {mint230(1)};
        SUF.shrink_to_fit();
    }
    void merge(RollingHash& b) {
        if (size() < b.size()) {
            pre.swap(b.pre);
            suf.swap(b.suf);
            PRE.swap(b.PRE);
            SUF.swap(b.SUF);
            reverse(b.suf.begin(), b.suf.end());
            for (auto& c : b.suf) push_front(c);
            for (auto& c : b.pre) push_front(c);
        } else {
            reverse(b.pre.begin(), b.pre.end());
            for (auto& c : b.pre) push_back(c);
            for (auto& c : b.suf) push_back(c);
        }
        b.clear();
    }
};

#line 2 "math/modint230.hpp"
#include<bits/stdc++.h>
using namespace std;
long long modint_MOD = (1LL<<61)-1;
// mod の値を変更する(デフォルトは2^61-1)
void setmod(long long x) { modint_MOD = x; }
struct mint230 {
    long long val;
    mint230(long long x=0) {
        val=(x%modint_MOD+modint_MOD)%modint_MOD;
    }
    mint230& operator+=(const mint230& a) { val = (val + a.val) % modint_MOD; return *this; }
    mint230& operator-=(const mint230& a) { val = (val - a.val + modint_MOD) % modint_MOD; return *this; }
    mint230& operator*=(const mint230& a) { val = (__int128_t)val * a.val % modint_MOD ; return *this; }
    mint230& operator/=(const mint230& a) { return *this *= a.inv(); }
    mint230 operator+(const mint230& a) const { return mint230(*this) += a; }
    mint230 operator-(const mint230& a) const { return mint230(*this) -= a; }
    mint230 operator*(const mint230& a) const { return mint230(*this) *= a; }
    mint230 operator/(const mint230& a) const { return mint230(*this) /= a; }
    bool operator==(const mint230& a) const { return val == a.val; }
    bool operator!=(const mint230& a) const { return val != a.val; }
    mint230& operator+=(int a) { return *this += mint230(a); }
    mint230& operator-=(int a) { return *this -= mint230(a); }
    mint230& operator*=(int a) { return *this *= mint230(a); }
    mint230& operator/=(int a) { return *this /= mint230(a); }
    mint230 operator+(int a) const { return mint230(*this) += a; }
    mint230 operator-(int a) const { return mint230(*this) -= a; }
    mint230 operator*(int a) const { return mint230(*this) *= a; }
    mint230 operator/(int a) const { return mint230(*this) /= a; }
    bool operator==(int a) const { return val == mint230(a).val; }
    bool operator!=(int a) const { return val != mint230(a).val; }
    friend mint230 operator+(int a,const mint230& b) { return mint230(a) + b; }
    friend mint230 operator-(int a,const mint230& b) { return mint230(a) - b; }
    friend mint230 operator*(int a,const mint230& b) { return mint230(a) * b; }
    friend mint230 operator/(int a,const mint230& b) { return mint230(a) / b; }
    friend bool operator==(int a, const mint230& b) { return mint230(a) == b; }
    friend bool operator!=(int a, const mint230& b) { return mint230(a) != b; }
    mint230& operator++() { return *this += 1; }
    mint230 operator++(int) { mint230 r = *this; *this += 1; return r; }
    mint230& operator--() { return *this -= 1; }
    mint230 operator--(int) { mint230 r = *this; *this -= 1; return r; }
    // modpow を計算する。計算量O(log mod)
    mint230 pow(long long n) const {
        if (n != 0) n = ((n-2) % (modint_MOD-1) + modint_MOD) % (modint_MOD-1) + 1;
        mint230 r = 1, a = *this;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint230 inv() const { return pow(-1); }
    friend ostream& operator<<(ostream&s, const mint230& a) { return s << a.val; }
    friend istream& operator>>(istream&s, mint230& a) { long long x; s >> x; a = mint230(x); return s; }
};
vector<mint230>fac, ifac;
// n までの階乗を前計算する。O(n)
void buildfac(int n) {
    fac.resize(n + 1);
    ifac.resize(n + 1);
    fac[0] = 1;
    for (int i=1; i<=n; i++) fac[i] = fac[i-1] * i;
    ifac[n] = mint230(1) / fac[n];
    for (int i=n; 0<i; i--) ifac[i-1] = ifac[i] * i;
}
// nCk を求める。buildfacの呼び出しが必須。O(1)
mint230 comb(int n,int k) { return (0 <= k && k <= n ) ? fac[n] * ifac[k] * ifac[n-k] : 0; }
// nPk を求める。buildfacの呼び出しが必須。O(1)
mint230 perm(int n,int k) { return (0 <= k && k <= n ) ? fac[n] * ifac[n-k] : 0; }
#line 4 "string/rollinghash.hpp"
using namespace std;
template <typename T = char>
struct RollingHash {
    mint230 generate_base() {
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<uint64_t> rand(1, mint230::mod() - 1);
        return mint230(rand(mt));
    }
    mint230 base, base_inv;
    vector<mint230> bases, base_invs;
    vector<T> pre, suf;
    vector<mint230> PRE{mint230(0)}, SUF{mint230(0)};
    void expand_bases(size_t n) {
        if (bases.size() < n+1) {
            int pre_sz = (int)bases.size();
            bases.resize(n + 1);
            for (int i=pre_sz-1; i<n; i++) {
                bases[i+1] = bases[i] * base;
            }
        }
    }
    void expand_base_invs(size_t n) {
        if (base_invs.size() < n+1) {
            int pre_sz = (int)base_invs.size();
            base_invs.resize(n+1);
            for (int i=pre_sz-1; i<n; i++) {
                base_invs[i+1] = base_invs[i] * base_inv;
            }
        }
    }
    RollingHash(const string& s) {
        for (auto& c : s) push_back(c);
    }
    RollingHash(const vector<T>& s) {
        for (auto& c : s) push_back(c);
    }
    int size() { return (int)pre.size() + (int)suf.size(); }
    void push_front(T c) {
        expand_base_invs(pre.size()+1);
        PRE.push_back(PRE.back() + base_invs[pre.size()+1] * mint230(c));
        pre.push_back(c);
    }
    void push_back(T c) {
        expand_bases(suf.size());
        SUF.push_back(SUF.back() + bases[suf.size()] * mint230(c));
        suf.push_back(c);
    }
    T operator[](int k) {
        assert(0<=k && k<size());
        k -= pre.size();
        return (k < 0 ? pre[~k] : suf[k]);
    }
    mint230 get(int r) {
        assert(0<=r && r<=size());
        r -= (int)pre.size();
        expand_bases(pre.size());
        if (r < 0) {
            return bases[pre.size()] * (PRE.back() - PRE[-r]);
        } else {
            return bases[pre.size()] * (PRE.back() + SUF[r]);
        }
    }
    mint230 get(int l, int r) {
        assert(0 <= l and l <= r and r <= size());
        expand_base_invs(l);
        return base_invs[l] * (get(r) - get(l));
    }
    int lcp(const RollingHash& b) {
        int len = min(size(), b.size());
        int low = 0, high = len + 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (get(mid) == b.get(mid)){
                low = mid;
            }
            else {
                high = mid;
            }
        }
        return low;
    }
    int lcp(const RollingHash& b, int l1, int l2) {
        assert(l1 <= size());
        assert(l2 <= b.size());
        int len = min(size() - l1, b.size() - l2);
        int low = 0, 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;
    }
    mint230 combine(mint230 h1, int h1_len, mint230 h2) {
        expand_bases(h1_len);
        return h1 + h2 * bases[h1_len];
    }
    void clear() {
        pre.clear();
        pre.shrink_to_fit();
        suf.clear();
        suf.shrink_to_fit();
        PRE = {mint230(1)};
        PRE.shrink_to_fit();
        SUF = {mint230(1)};
        SUF.shrink_to_fit();
    }
    void merge(RollingHash& b) {
        if (size() < b.size()) {
            pre.swap(b.pre);
            suf.swap(b.suf);
            PRE.swap(b.PRE);
            SUF.swap(b.SUF);
            reverse(b.suf.begin(), b.suf.end());
            for (auto& c : b.suf) push_front(c);
            for (auto& c : b.pre) push_front(c);
        } else {
            reverse(b.pre.begin(), b.pre.end());
            for (auto& c : b.pre) push_back(c);
            for (auto& c : b.suf) push_back(c);
        }
        b.clear();
    }
};

Back to top page