polynomial_string_hash.cpp

/**
 * Polynomial rolling hash: H = sum s[i]*p^i mod m (0-based from left).
 */
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

static const std::uint64_t kMod = 1'000'000'007ULL;
static const std::uint64_t kBase = 131ULL;

static std::uint64_t polyHash(const std::string& s) {
    std::uint64_t h = 0;
    std::uint64_t p = 1;
    for (unsigned char c : s) {
        h = (h + static_cast<std::uint64_t>(c + 1) * p) % kMod;
        p = (p * kBase) % kMod;
    }
    return h;
}

// Prefix hashes: pref[i] = hash of s[0..i]
static std::vector<std::uint64_t> prefixHashes(const std::string& s) {
    std::vector<std::uint64_t> pref(s.size());
    std::uint64_t h = 0;
    std::uint64_t pw = 1;
    for (std::size_t i = 0; i < s.size(); ++i) {
        unsigned char c = static_cast<unsigned char>(s[i]);
        h = (h + static_cast<std::uint64_t>(c + 1) * pw) % kMod;
        pref[i] = h;
        pw = (pw * kBase) % kMod;
    }
    return pref;
}

int main() {
    std::string s = "apple";
    std::cout << "H(\"" << s << "\") = " << polyHash(s) << " (mod " << kMod << ")\n";
    auto pref = prefixHashes("banana");
    for (std::size_t i = 0; i < pref.size(); ++i) {
        std::cout << "pref[" << i << "] = " << pref[i] << "\n";
    }
    return 0;
}