Cpp-algorithms/hashing.cpp at master · SpeedOfMagic/Cpp-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class RingNumber {
 private:
    uint64_t number_ = 0;
    const static uint64_t mod_ = 1000000007;

 public:
    constexpr RingNumber() = default;

    template<typename T>
    constexpr RingNumber(T number) : number_(number % mod_) {}

    operator uint64_t() const noexcept { return number_; }

    template<typename Number>
    inline RingNumber operator+(const Number& other) const noexcept {
        return (number_ + other % mod_) % mod_;
    }

    template<typename Number>
    inline RingNumber operator-(const Number& other) const noexcept {
        return (number_ + mod_ - other % mod_) % mod_;
    }

    template<typename Number>
    inline RingNumber operator*(const Number& other) const noexcept {
        return (number_ * (other % mod_)) % mod_;
    }

    template<typename Number>
    inline RingNumber operator+=(const Number& other) noexcept { return (*this) = (*this) + other; }

    template<typename Number>
    inline RingNumber operator-=(const Number& other) noexcept { return (*this) = (*this) - other; }

    template<typename Number>
    inline RingNumber operator*=(const Number& other) noexcept { return (*this) = (*this) * other; }
};


class Hasher : public vector<RingNumber> {
 private:
    const constexpr static RingNumber base_ = 31;
    inline static vector<RingNumber> pow_of_base_;

 public:
    inline static RingNumber hashChar(char c) { return c - 'a' + 1; }

    Hasher(const string& str) {
        resize(str.size());
        operator[](0) = hashChar(str[0]);
        for (size_t i = 1; i < str.size(); ++i)
            operator[](i) = operator[](i - 1) * base_ + hashChar(str[i]);

        while (pow_of_base_.size() < str.size()) {
            if (pow_of_base_.empty())
                pow_of_base_.push_back(1);
            else
                pow_of_base_.push_back(pow_of_base_.back() * base_);
        }
    }

    inline RingNumber getHash(size_t l, size_t r) const {
        return operator[](r) - (l ? operator[](l - 1) * pow_of_base_[r - l + 1] : RingNumber());
    }

    inline RingNumber getHash(size_t l) const { return getHash(l, size() - 1); }
};