← all categories

String Hashing 7f2ead7c

Polynomial string hashing, arithmetic mod 2^64-1 (not mod 2^64 — plain mod-2^64 overflow hashing is broken by well-known adversarial test data, e.g. Thue-Morse strings, and mod-1e9+7-style double hashing is routinely hacked when the mod/base are common template defaults). H wraps the mod-(2^64-1) arithmetic; compare hashes via == and <. HashInterval(s).hashInterval(a, b) hashes s[a, b). Source: kactl (CC0), see NOTICE.md.

Time: O(n) build, O(1) per interval hash. kactl-derived, tested

content/strings/string-hashing.h

typedef uint64_t ull;
struct H {
    ull x;
    H(ull x = 0) : x(x) {}
    H operator+(H o) { return x + o.x + (x + o.x < x); }
    H operator-(H o) { return *this + ~o.x; }
    H operator*(H o) { auto m = (__uint128_t)x * o.x; return H((ull)m) + (ull)(m >> 64); }
    ull get() const { return x + !~x; }
    bool operator==(H o) const { return get() == o.get(); }
    bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11 + 3;  // order ~3e9; a random base also works

struct HashInterval {
    vector<H> ha, pw;
    HashInterval(string &s) : ha(s.size() + 1), pw(ha) {
        pw[0] = 1;
        for (int i = 0; i < (int)s.size(); i++) {
            ha[i + 1] = ha[i] * C + s[i];
            pw[i + 1] = pw[i] * C;
        }
    }
    H hashInterval(int a, int b) { return ha[b] - ha[a] * pw[b - a]; }  // hash s[a, b)
};

vector<H> slidingHashes(string &s, int length) {
    if ((int)s.size() < length) return {};
    H h = 0, pw = 1;
    for (int i = 0; i < length; i++) { h = h * C + s[i]; pw = pw * C; }
    vector<H> res = {h};
    for (int i = length; i < (int)s.size(); i++) res.push_back(h = h * C + s[i] - pw * s[i - length]);
    return res;
}