prefix_double_hash.cpp

/**
 * Prefix hashes under two (mod, base) pairs + O(1) substring hash + equality check.
 * Double-hash reduces false positives when comparing substrings by hash only.
 */
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct HashParams {
    std::uint64_t mod;
    std::uint64_t base;
};

static std::uint64_t modMul(std::uint64_t a, std::uint64_t b, std::uint64_t mod) {
    return (a * b) % mod;
}

struct DoubleRolling {
    std::string s;
    HashParams h0{1'000'000'007ULL, 131ULL};
    HashParams h1{1'000'000'009ULL, 137ULL};
    std::vector<std::uint64_t> pref0, pref1, pow0, pow1;

    explicit DoubleRolling(std::string str) : s(std::move(str)) {
        build(h0, pref0, pow0);
        build(h1, pref1, pow1);
    }

    void build(const HashParams& hp, std::vector<std::uint64_t>& pref, std::vector<std::uint64_t>& pw) {
        const std::size_t n = s.size();
        pref.assign(n + 1, 0);
        pw.assign(n + 1, 1);
        for (std::size_t i = 1; i <= n; ++i) {
            pw[i] = modMul(pw[i - 1], hp.base, hp.mod);
            unsigned char c = static_cast<unsigned char>(s[i - 1]);
            pref[i] = (modMul(pref[i - 1], hp.base, hp.mod) + static_cast<std::uint64_t>(c) + 1) % hp.mod;
        }
    }

    // hash of s[l..r)  (0-based half-open)
    std::pair<std::uint64_t, std::uint64_t> substrHash(std::size_t l, std::size_t r) const {
        std::size_t len = r - l;
        std::uint64_t x0 =
            (pref0[r] + h0.mod - modMul(pref0[l], pow0[len], h0.mod)) % h0.mod;
        std::uint64_t x1 =
            (pref1[r] + h1.mod - modMul(pref1[l], pow1[len], h1.mod)) % h1.mod;
        return {x0, x1};
    }
};

int main() {
    std::string s = "banana";
    DoubleRolling dr(s);
    for (std::size_t len = 1; len <= s.size(); ++len) {
        auto a = dr.substrHash(0, len);
        auto b = dr.substrHash(s.size() - len, s.size());
        std::cout << "prefix vs suffix len " << len << " hashes (" << a.first << "," << a.second << ") vs ("
                  << b.first << "," << b.second << ") "
                  << (a == b ? "equal" : "differ") << "\n";
    }
    return 0;
}