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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107 | #pragma once
#include <compare><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "snippet/aliases.hpp"
#include "internal/dev_env.hpp"
#include "algebraic/base.hpp"
#include "numeric/fast_prime.hpp"
#include "numeric/modular/modint.hpp"
#include "random/engine.hpp"
namespace uni {
namespace algebraic {
template<uni::internal::modint_family ValueType, typename ValueType::value_type BASE>
struct rolling_hash_impl {
using value_type = ValueType;
inline static value_type base;
private:
value_type _value = 0, _power = 1;
public:
rolling_hash_impl(const value_type& value, const value_type& power) noexcept(NO_EXCEPT)
: _value(value), _power(power)
{
if(rolling_hash_impl::base == 0) {
if constexpr(BASE == 0) {
rolling_hash_impl::base = uni::primitive_root<true>(value_type::mod());
}
else if constexpr(BASE < 0) {
random_engine_64bit random(std::random_device{}());
rolling_hash_impl::base = static_cast<value_type>(random() % value_type::mod());
}
else {
rolling_hash_impl::base = BASE;
}
}
}
rolling_hash_impl(const value_type& value) noexcept(NO_EXCEPT) : rolling_hash_impl(value, 0) {<--- Struct 'rolling_hash_impl' has a constructor with 1 argument that is not explicit. [+]Struct 'rolling_hash_impl' has a constructor with 1 argument that is not explicit. Such, so called "Converting constructors", should in general be explicit for type safety reasons as that prevents unintended implicit conversions.
this->_power = rolling_hash_impl::base;
};
rolling_hash_impl() noexcept = default;
inline auto power() const noexcept(NO_EXCEPT) { return this->_power; }
inline auto val() const noexcept(NO_EXCEPT) { return this->_value; }
friend inline bool operator==(const rolling_hash_impl& lhs, const rolling_hash_impl& rhs) noexcept(NO_EXCEPT) {
return lhs._power == rhs._power && lhs._value == rhs._value;
}
friend inline auto operator<=>(const rolling_hash_impl& lhs, const rolling_hash_impl& rhs) noexcept(NO_EXCEPT) {
const auto comp_power = lhs._power <=> rhs._power;
if(comp_power != 0) return comp_power;
return lhs._value <=> rhs._value;
}
};
template<
bool REVERSE = false,
uni::internal::modint_family T = uni::static_modint_64bit<(1UL << 61) - 1>,
typename T::value_type BASE = 0
>
struct rolling_hash : base<rolling_hash_impl<T, BASE>>, scalar_multipliable<rolling_hash<REVERSE, T, BASE>>::automatic, associative {
using base<rolling_hash_impl<T, BASE>>::base;
rolling_hash(const T& v) : base<rolling_hash_impl<T, BASE>>(v) {}<--- Struct 'rolling_hash' has a constructor with 1 argument that is not explicit. [+]Struct 'rolling_hash' has a constructor with 1 argument that is not explicit. Such, so called "Converting constructors", should in general be explicit for type safety reasons as that prevents unintended implicit conversions.
template<class U>
requires (
(!std::same_as<std::remove_cvref_t<U>, T>) &&
(!std::constructible_from<rolling_hash_impl<T, BASE>, U>)
)
rolling_hash(U&& v) : base<rolling_hash_impl<T, BASE>>(hash64(std::forward<U>(v))) {}<--- Struct 'rolling_hash' has a constructor with 1 argument that is not explicit. [+]Struct 'rolling_hash' has a constructor with 1 argument that is not explicit. Such, so called "Converting constructors", should in general be explicit for type safety reasons as that prevents unintended implicit conversions.
friend inline auto operator+(const rolling_hash& lhs, const rolling_hash& rhs) noexcept(NO_EXCEPT) {
const auto power = lhs->power() * rhs->power();
if constexpr(REVERSE) return rolling_hash({ lhs->val() * rhs->power() + rhs->val(), power });
return rolling_hash({ lhs->val() + rhs->val() * lhs->power(), power });
}
inline auto operator-() noexcept(NO_EXCEPT) {
const auto power_inv = this->val().power().inv();
return rolling_hash({ -this->val().val() * power_inv, power_inv });
}
};
} // namespace algebraic
} // namespace uni
|