-
Notifications
You must be signed in to change notification settings - Fork 0
/
hashing.cpp
68 lines (51 loc) · 2.06 KB
/
hashing.cpp
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); }
};