Static Rolling Hash
(string/rolling_hash.hpp)

View this file on GitHub
Last update: 2026-06-13 20:51:48+09:00
Include: #include "string/rolling_hash.hpp"

Overview

A robust data structure that precomputes the hash values of a string’s prefixes to answer substring hash queries in $O(1)$ time. It uses __int128_t internally to safely prevent integer overflow.

In addition to standard substring hashes, this class supports advanced operations such as finding the Longest Common Prefix (LCP), lexicographical comparison, and string repetition in $O(\log N)$ time. It also provides static helpers for calculating hashes dynamically and powering the monoid::RollingHash.

Template Parameters

Base: The hash base. Default is 10007.
Mod: The modulo for the hash. Default is (1LL << 61) - 1 (a Mersenne prime for extreme collision resistance).

Instance Methods

Method	Description	Complexity
`RollingHash(const std::string& s)`	Builds prefix hashes and base powers for `s`, and keeps a copy for character comparisons.	$O(N)$ time and space
`long long get(int l, int r) const`	Returns the hash of substring `[l, r)`.	$O(1)$
`long long concat(int l1, int r1, int l2, int r2) const`	Returns the hash of `[l1, r1)` followed by `[l2, r2)`.	$O(1)$
`int lcp(int l1, int r1, int l2, int r2) const`	Returns the longest common prefix length of two substrings.	$O(\log(\min(r1 - l1, r2 - l2)))$
`int compare(int l1, int r1, int l2, int r2) const`	Lexicographically compares two substrings. Returns `-1`, `0`, or `1`.	$O(\log N)$
`long long repeat(int l, int r, long long k) const`	Returns the hash of substring `[l, r)` repeated `k` times.	$O(\log k)$

Static Helper Methods

Method	Description	Complexity
`static long long compute_hash(const std::string& str)`	Computes the hash of `str` without building prefix arrays.	$O(N)$ time, $O(1)$ auxiliary space
`static constexpr long long combine(long long h1, long long h2, long long base_power2)`	Returns the hash of a left string with hash `h1` followed by a right string with hash `h2`. `base_power2` is $Base^{\text{right length}} \bmod Mod$.	$O(1)$
`static constexpr long long repeat_hash(long long h, long long p, long long k)`	Returns the hash of a string with hash `h` repeated `k` times. `p` is $Base^{\text{string length}} \bmod Mod$.	$O(\log k)$

Example

#include "string/rolling_hash.hpp"
#include <iostream>
#include <string>

using RH = m1une::string::RollingHash<10007, 998244353>;

int main() {
    std::string S = "abracadabra";
    RH rh(S);

    // Basic substring hash
    std::cout << (rh.get(0, 3) == rh.get(7, 10)) << "\n"; // Output: 1 (True, "abr" == "abr")

    // LCP of S[0..4] ("abrac") and S[7..11] ("abra")
    std::cout << rh.lcp(0, 5, 7, 11) << "\n"; // Output: 4

    // Lexicographical compare ("abrac" > "abra")
    std::cout << rh.compare(0, 5, 7, 11) << "\n"; // Output: 1

    // Substring repetition (Hash of "abr" repeated 100 times)
    long long repeated = rh.repeat(0, 3, 100);

    // Static compute hash (O(1) space)
    long long pattern = RH::compute_hash("cad");
    std::cout << repeated << " " << pattern << "\n";

    return 0;
}

Required by

Verified with

Code

#ifndef M1UNE_STRING_ROLLING_HASH_HPP
#define M1UNE_STRING_ROLLING_HASH_HPP 1

#include <algorithm>
#include <string>
#include <utility>
#include <vector>

namespace m1une {
namespace string {

// Standard Rolling Hash for static strings.
// Precomputes hashes to answer substring queries in O(1).
// Provides advanced operations like LCP, lexicographical comparison, and string repetition in O(log N).
template <long long Base = 10007, long long Mod = (1LL << 61) - 1>
struct RollingHash {
    std::string s;
    std::vector<long long> hash;
    std::vector<long long> power;

    RollingHash() = default;

    // Constructs the rolling hash table for the given string.
    explicit RollingHash(const std::string& str) : s(str) {
        int n = s.size();
        hash.assign(n + 1, 0);
        power.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            // Use __int128_t to prevent overflow during multiplication
            hash[i + 1] = (static_cast<__int128_t>(hash[i]) * Base + s[i]) % Mod;
            power[i + 1] = (static_cast<__int128_t>(power[i]) * Base) % Mod;
        }
    }

    // Returns the hash of the substring S[l..r) in O(1).
    long long get(int l, int r) const {
        long long res = hash[r] - (static_cast<__int128_t>(hash[l]) * power[r - l]) % Mod;
        if (res < 0) res += Mod;
        return res;
    }

    // Returns the hash of the concatenated substrings S[l1..r1) and S[l2..r2).
    long long concat(int l1, int r1, int l2, int r2) const {
        long long h1 = get(l1, r1);
        long long h2 = get(l2, r2);
        return combine(h1, h2, power[r2 - l2]);
    }

    // Calculates the Longest Common Prefix (LCP) length of S[l1..r1) and S[l2..r2) in O(log N).
    int lcp(int l1, int r1, int l2, int r2) const {
        int len = std::min(r1 - l1, r2 - l2);
        int low = 0, high = len + 1;
        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            if (get(l1, l1 + mid) == get(l2, l2 + mid)) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    }

    // Lexicographically compares S[l1..r1) and S[l2..r2) in O(log N).
    // Returns -1 if S[l1..r1) < S[l2..r2), 0 if equal, and 1 if S[l1..r1) > S[l2..r2).
    int compare(int l1, int r1, int l2, int r2) const {
        int l = lcp(l1, r1, l2, r2);
        bool end1 = (l1 + l == r1);
        bool end2 = (l2 + l == r2);
        if (end1 && end2) return 0;
        if (end1) return -1;
        if (end2) return 1;
        return s[l1 + l] < s[l2 + l] ? -1 : 1;
    }

    // Returns the hash of the substring S[l..r) repeated 'k' times.
    long long repeat(int l, int r, long long k) const {
        long long h = get(l, r);
        long long p = power[r - l];
        return repeat_hash(h, p, k);
    }

    // --- Static Helpers for dynamic processing and Monoid integration ---

    // Computes the hash of a single string in O(N) time and O(1) space.
    static long long compute_hash(const std::string& str) {
        long long h = 0;
        for (char c : str) {
            h = (static_cast<__int128_t>(h) * Base + c) % Mod;
        }
        return h;
    }

    // Combines two hashes. Equivalent to concatenating string 'b' to the right of string 'a'.
    static constexpr long long combine(long long h1, long long h2, long long base_power2) {
        return (static_cast<__int128_t>(h1) * base_power2 + h2) % Mod;
    }

    // Returns the hash of a string (with hash 'h' and base_power 'p') repeated 'k' times.
    static constexpr long long repeat_hash(long long h, long long p, long long k) {
        long long res_h = 0;
        long long res_p = 1;
        long long cur_h = h;
        long long cur_p = p;
        while (k > 0) {
            if (k & 1) {
                res_h = combine(res_h, cur_h, cur_p);
                res_p = (static_cast<__int128_t>(res_p) * cur_p) % Mod;
            }
            cur_h = combine(cur_h, cur_h, cur_p);
            cur_p = (static_cast<__int128_t>(cur_p) * cur_p) % Mod;
            k >>= 1;
        }
        return res_h;
    }

    // Creates the state pair {hash_value, base_power} for a single character.
    static constexpr std::pair<long long, long long> make_single(long long c) {
        return {c % Mod, Base % Mod};
    }
};

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_ROLLING_HASH_HPP

#line 1 "string/rolling_hash.hpp"



#include <algorithm>
#include <string>
#include <utility>
#include <vector>

namespace m1une {
namespace string {

// Standard Rolling Hash for static strings.
// Precomputes hashes to answer substring queries in O(1).
// Provides advanced operations like LCP, lexicographical comparison, and string repetition in O(log N).
template <long long Base = 10007, long long Mod = (1LL << 61) - 1>
struct RollingHash {
    std::string s;
    std::vector<long long> hash;
    std::vector<long long> power;

    RollingHash() = default;

    // Constructs the rolling hash table for the given string.
    explicit RollingHash(const std::string& str) : s(str) {
        int n = s.size();
        hash.assign(n + 1, 0);
        power.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            // Use __int128_t to prevent overflow during multiplication
            hash[i + 1] = (static_cast<__int128_t>(hash[i]) * Base + s[i]) % Mod;
            power[i + 1] = (static_cast<__int128_t>(power[i]) * Base) % Mod;
        }
    }

    // Returns the hash of the substring S[l..r) in O(1).
    long long get(int l, int r) const {
        long long res = hash[r] - (static_cast<__int128_t>(hash[l]) * power[r - l]) % Mod;
        if (res < 0) res += Mod;
        return res;
    }

    // Returns the hash of the concatenated substrings S[l1..r1) and S[l2..r2).
    long long concat(int l1, int r1, int l2, int r2) const {
        long long h1 = get(l1, r1);
        long long h2 = get(l2, r2);
        return combine(h1, h2, power[r2 - l2]);
    }

    // Calculates the Longest Common Prefix (LCP) length of S[l1..r1) and S[l2..r2) in O(log N).
    int lcp(int l1, int r1, int l2, int r2) const {
        int len = std::min(r1 - l1, r2 - l2);
        int low = 0, high = len + 1;
        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            if (get(l1, l1 + mid) == get(l2, l2 + mid)) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    }

    // Lexicographically compares S[l1..r1) and S[l2..r2) in O(log N).
    // Returns -1 if S[l1..r1) < S[l2..r2), 0 if equal, and 1 if S[l1..r1) > S[l2..r2).
    int compare(int l1, int r1, int l2, int r2) const {
        int l = lcp(l1, r1, l2, r2);
        bool end1 = (l1 + l == r1);
        bool end2 = (l2 + l == r2);
        if (end1 && end2) return 0;
        if (end1) return -1;
        if (end2) return 1;
        return s[l1 + l] < s[l2 + l] ? -1 : 1;
    }

    // Returns the hash of the substring S[l..r) repeated 'k' times.
    long long repeat(int l, int r, long long k) const {
        long long h = get(l, r);
        long long p = power[r - l];
        return repeat_hash(h, p, k);
    }

    // --- Static Helpers for dynamic processing and Monoid integration ---

    // Computes the hash of a single string in O(N) time and O(1) space.
    static long long compute_hash(const std::string& str) {
        long long h = 0;
        for (char c : str) {
            h = (static_cast<__int128_t>(h) * Base + c) % Mod;
        }
        return h;
    }

    // Combines two hashes. Equivalent to concatenating string 'b' to the right of string 'a'.
    static constexpr long long combine(long long h1, long long h2, long long base_power2) {
        return (static_cast<__int128_t>(h1) * base_power2 + h2) % Mod;
    }

    // Returns the hash of a string (with hash 'h' and base_power 'p') repeated 'k' times.
    static constexpr long long repeat_hash(long long h, long long p, long long k) {
        long long res_h = 0;
        long long res_p = 1;
        long long cur_h = h;
        long long cur_p = p;
        while (k > 0) {
            if (k & 1) {
                res_h = combine(res_h, cur_h, cur_p);
                res_p = (static_cast<__int128_t>(res_p) * cur_p) % Mod;
            }
            cur_h = combine(cur_h, cur_h, cur_p);
            cur_p = (static_cast<__int128_t>(cur_p) * cur_p) % Mod;
            k >>= 1;
        }
        return res_h;
    }

    // Creates the state pair {hash_value, base_power} for a single character.
    static constexpr std::pair<long long, long long> make_single(long long c) {
        return {c % Mod, Base % Mod};
    }
};

}  // namespace string
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Static Rolling Hash
(string/rolling_hash.hpp)

Overview

Template Parameters

Instance Methods

Static Helper Methods

Example

Required by

Verified with

Code

Static Rolling Hash (string/rolling_hash.hpp)

Overview

Template Parameters

Instance Methods

Static Helper Methods

Example

Required by

Verified with

Code

Static Rolling Hash
(string/rolling_hash.hpp)