String Hash
(string/string_hash.hpp)

• View this file on GitHub
• Last update: 2026-10-24 20:17:47+09:00
• Include: #include "string/string_hash.hpp"

概要

• 文字列のハッシュ値。rolling_hash と range_update_range_hash が返す。

使い方

• string_hash<k = 1, mint = modint2305843009213693951>: 基数 $k$ 個でのハッシュ値。val[i] が $i$ 番目の基数での値、len が文字列の長さ。
• string_hash(): 空文字列のハッシュ値を作る。
• string_hash(c): 1 文字 c のハッシュ値を作る。
• string_hash::repeat(c, n): 文字 c を $n$ 個並べた文字列のハッシュ値を返す。
• a + b: 連結した文字列のハッシュ値を返す。
• a == b: 長さと val がすべて等しいかを返す。
• a < b: set や map のキーにするための全順序。
• lcp(a, l1, r1, b, l2, r2): a の [l1, r1) と b の [l2, r2) の最長共通接頭辞の長さを返す。a, b は rolling_hash か range_update_range_hash。
• cmp(a, l1, r1, b, l2, r2): a の [l1, r1) と b の [l2, r2) を辞書順で比較し、$-1, 0, 1$ のいずれかを返す。

制約

• 文字は $0 \le c <$ mint::mod()

計算量

• a + b, repeat: $\mathcal{O}(k)$
• lcp, cmp: prod を $\mathcal{O}(\log N)$ 回

Depends on

• modint2305843009213693951 (math/modint2305843009213693951.hpp)

Required by

• Range Update Range Hash (string/range_update_range_hash.hpp)
• Rolling Hash (string/rolling_hash.hpp)

Verified with

• test/aoj/0355.test.cpp
• test/library-checker/enumerate_palindromes.test.cpp
• test/library-checker/suffix_array_rolling_hash.test.cpp
• test/library-checker/zalgorithm_rolling_hash.test.cpp
• test/unit/string_hash.test.cpp
• test/yukicoder/2231.test.cpp

Code

#pragma once
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <random>
#include <vector>

#include "math/modint2305843009213693951.hpp"
template <int k = 1, class mint = modint2305843009213693951>
struct string_hash {
    static_assert(k >= 1);
    std::array<mint, k> val;
    int len;
    string_hash() : val{}, len(0) {}
    explicit string_hash(int c) : len(1) {
        val.fill(mint(c));
    }
    static string_hash repeat(int c, int n) {
        assert(0 <= n);
        string_hash h;
        h.len = n;
        for (int i = 0; i < k; i++) h.val[i] = mint(c) * pow_sum(i, n);
        return h;
    }
    friend string_hash operator+(const string_hash& a, const string_hash& b) {
        string_hash r;
        r.len = a.len + b.len;
        for (int i = 0; i < k; i++) r.val[i] = a.val[i] * pow(i, b.len) + b.val[i];
        return r;
    }
    string_hash& operator+=(const string_hash& b) {
        return *this = *this + b;
    }
    friend bool operator==(const string_hash& a, const string_hash& b) {
        return a.len == b.len && a.val == b.val;
    }
    friend bool operator<(const string_hash& a, const string_hash& b) {
        if (a.len != b.len) return a.len < b.len;
        for (int i = 0; i < k; i++) {
            if (a.val[i] != b.val[i]) return a.val[i].val() < b.val[i].val();
        }
        return false;
    }
    static mint base(int i) {
        return bases()[i];
    }
    static mint pow(int i, int n) {
        ensure(n);
        return pows()[i][n];
    }
    static mint pow_sum(int i, int n) {
        ensure(n);
        return pow_sums()[i][n];
    }

private:
    static std::array<mint, k> gen_bases() {
        std::mt19937_64 rng(std::random_device{}());
        std::array<mint, k> b;
        for (int i = 0; i < k; i++) {
            while (true) {
                uint64_t e = std::uniform_int_distribution<uint64_t>(1, mint::mod() - 1)(rng);
                if (std::gcd(e, uint64_t(mint::mod() - 1)) != 1) continue;
                b[i] = mint(37).pow(e);
                break;
            }
        }
        return b;
    }
    static std::array<mint, k>& bases() {
        static std::array<mint, k> b = gen_bases();
        return b;
    }
    static std::array<std::vector<mint>, k>& pows() {
        static std::array<std::vector<mint>, k> p = [] {
            std::array<std::vector<mint>, k> p;
            for (auto& v : p) v.assign(1, mint(1));
            return p;
        }();
        return p;
    }
    static std::array<std::vector<mint>, k>& pow_sums() {
        static std::array<std::vector<mint>, k> s = [] {
            std::array<std::vector<mint>, k> s;
            for (auto& v : s) v.assign(1, mint(0));
            return s;
        }();
        return s;
    }
    static void ensure(int n) {
        auto& p = pows();
        auto& s = pow_sums();
        int sz = int(p[0].size());
        if (n < sz) return;
        int m = std::max(n + 1, 2 * sz);
        for (int i = 0; i < k; i++) {
            p[i].resize(m);
            s[i].resize(m);
            for (int j = sz; j < m; j++) {
                p[i][j] = p[i][j - 1] * base(i);
                s[i][j] = s[i][j - 1] + p[i][j - 1];
            }
        }
    }
};
template <class A, class B>
int lcp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int ok = 0, ng = std::min(r1 - l1, r2 - l2) + 1;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        (a.prod(l1, l1 + mid) == b.prod(l2, l2 + mid) ? ok : ng) = mid;
    }
    return ok;
}
template <class A, class B>
int cmp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int x = lcp(a, l1, r1, b, l2, r2);
    bool ea = l1 + x == r1, eb = l2 + x == r2;
    if (ea && eb) return 0;
    if (ea) return -1;
    if (eb) return 1;
    return a.get(l1 + x).val[0].val() < b.get(l2 + x).val[0].val() ? -1 : 1;
}

#line 2 "string/string_hash.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <random>
#include <vector>

#line 3 "math/modint2305843009213693951.hpp"
#include <concepts>
#line 5 "math/modint2305843009213693951.hpp"
struct modint2305843009213693951 {
    using mint = modint2305843009213693951;
    static constexpr uint64_t mod() {
        return m;
    }
    static mint raw(uint64_t v) {
        mint x;
        x._v = v;
        return x;
    }
    modint2305843009213693951() : _v(0) {}
    template <std::unsigned_integral T>
    modint2305843009213693951(T v) : _v(reduce(v)) {}
    template <std::signed_integral T>
    modint2305843009213693951(T v) {
        if (v >= 0) {
            _v = reduce(uint64_t(v));
        } else {
            uint64_t x = reduce(uint64_t(0) - uint64_t(v));
            _v = x == 0 ? 0 : m - x;
        }
    }
    uint64_t val() const {
        return _v;
    }
    mint& operator++() {
        if (++_v == m) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = m;
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint r = *this;
        ++*this;
        return r;
    }
    mint operator--(int) {
        mint r = *this;
        --*this;
        return r;
    }
    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= m) _v -= m;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += m - rhs._v;
        if (_v >= m) _v -= m;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
        constexpr uint64_t mask30 = (uint64_t(1) << 30) - 1;
        uint64_t au = _v >> 31, ad = _v & mask31;
        uint64_t bu = rhs._v >> 31, bd = rhs._v & mask31;
        uint64_t mid = ad * bu + au * bd;
        uint64_t mu = mid >> 30, md = mid & mask30;
        _v = reduce((au * bu << 1) + mu + (md << 31) + ad * bd);
        return *this;
    }
    mint& operator/=(const mint& rhs) {
        return *this *= rhs.inv();
    }
    mint operator+() const {
        return *this;
    }
    mint operator-() const {
        return mint() - *this;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        assert(_v != 0);
        return pow(m - 2);
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

private:
    static constexpr uint64_t m = (uint64_t(1) << 61) - 1;
    static constexpr uint64_t reduce(uint64_t v) {
        uint64_t x = (v >> 61) + (v & m);
        if (x >= m) x -= m;
        return x;
    }
    uint64_t _v;
};
#line 11 "string/string_hash.hpp"
template <int k = 1, class mint = modint2305843009213693951>
struct string_hash {
    static_assert(k >= 1);
    std::array<mint, k> val;
    int len;
    string_hash() : val{}, len(0) {}
    explicit string_hash(int c) : len(1) {
        val.fill(mint(c));
    }
    static string_hash repeat(int c, int n) {
        assert(0 <= n);
        string_hash h;
        h.len = n;
        for (int i = 0; i < k; i++) h.val[i] = mint(c) * pow_sum(i, n);
        return h;
    }
    friend string_hash operator+(const string_hash& a, const string_hash& b) {
        string_hash r;
        r.len = a.len + b.len;
        for (int i = 0; i < k; i++) r.val[i] = a.val[i] * pow(i, b.len) + b.val[i];
        return r;
    }
    string_hash& operator+=(const string_hash& b) {
        return *this = *this + b;
    }
    friend bool operator==(const string_hash& a, const string_hash& b) {
        return a.len == b.len && a.val == b.val;
    }
    friend bool operator<(const string_hash& a, const string_hash& b) {
        if (a.len != b.len) return a.len < b.len;
        for (int i = 0; i < k; i++) {
            if (a.val[i] != b.val[i]) return a.val[i].val() < b.val[i].val();
        }
        return false;
    }
    static mint base(int i) {
        return bases()[i];
    }
    static mint pow(int i, int n) {
        ensure(n);
        return pows()[i][n];
    }
    static mint pow_sum(int i, int n) {
        ensure(n);
        return pow_sums()[i][n];
    }

private:
    static std::array<mint, k> gen_bases() {
        std::mt19937_64 rng(std::random_device{}());
        std::array<mint, k> b;
        for (int i = 0; i < k; i++) {
            while (true) {
                uint64_t e = std::uniform_int_distribution<uint64_t>(1, mint::mod() - 1)(rng);
                if (std::gcd(e, uint64_t(mint::mod() - 1)) != 1) continue;
                b[i] = mint(37).pow(e);
                break;
            }
        }
        return b;
    }
    static std::array<mint, k>& bases() {
        static std::array<mint, k> b = gen_bases();
        return b;
    }
    static std::array<std::vector<mint>, k>& pows() {
        static std::array<std::vector<mint>, k> p = [] {
            std::array<std::vector<mint>, k> p;
            for (auto& v : p) v.assign(1, mint(1));
            return p;
        }();
        return p;
    }
    static std::array<std::vector<mint>, k>& pow_sums() {
        static std::array<std::vector<mint>, k> s = [] {
            std::array<std::vector<mint>, k> s;
            for (auto& v : s) v.assign(1, mint(0));
            return s;
        }();
        return s;
    }
    static void ensure(int n) {
        auto& p = pows();
        auto& s = pow_sums();
        int sz = int(p[0].size());
        if (n < sz) return;
        int m = std::max(n + 1, 2 * sz);
        for (int i = 0; i < k; i++) {
            p[i].resize(m);
            s[i].resize(m);
            for (int j = sz; j < m; j++) {
                p[i][j] = p[i][j - 1] * base(i);
                s[i][j] = s[i][j - 1] + p[i][j - 1];
            }
        }
    }
};
template <class A, class B>
int lcp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int ok = 0, ng = std::min(r1 - l1, r2 - l2) + 1;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        (a.prod(l1, l1 + mid) == b.prod(l2, l2 + mid) ? ok : ng) = mid;
    }
    return ok;
}
template <class A, class B>
int cmp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int x = lcp(a, l1, r1, b, l2, r2);
    bool ea = l1 + x == r1, eb = l2 + x == r2;
    if (ea && eb) return 0;
    if (ea) return -1;
    if (eb) return 1;
    return a.get(l1 + x).val[0].val() < b.get(l2 + x).val[0].val() ? -1 : 1;
}

Back to top page