#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #include "../../String/rolling-hash.hpp" #include "../../Util/randoms.hpp" #include "../../Util/all-macro.hpp" #include "../../Util/rep-macro.hpp" #include "../../Util/Debug/errln.hpp" using namespace std; namespace rnd = arumakan::random; using RH = RollingHash<17273747>; const auto testdatas = []() -> vector<pair<string, RH>> { string s1 = "a"; string s2 = "zzzzz"; string s3 = rnd::randomValueContainer<string>('a', 'b', 30, 50); string s4 = rnd::randomValueContainer<string>('x', 'z', 30, 50); return { {s1, RH(all(s1))}, {s2, RH(all(s2))}, {s3, RH(all(s3))}, {s4, RH(all(s4))}, }; }(); void test_hash() { for (const auto& [str, rolhash] : testdatas) { assert(rolhash.hash() == rolhash.rangeHash(0, str.length())); } errln("OK"); } void test_rangeHash_and_substr() { for (const auto& [str, rolhash] : testdatas) { const auto N = str.length(); rep(l1, 0, N) rep(r1, l1 + 1, N) { rep(l2, 0, N) rep(r2, l2 + 1, N) { const auto len1 = r1 - l1; const auto len2 = r2 - l2; const bool equality_expected = string_view(str).substr(l1, len1) == string_view(str).substr(l2, len2); const bool equality_rangeHash = rolhash.rangeHash(l1, r1) == rolhash.rangeHash(l2, r2); const bool equality_substr = rolhash.substr(l1, len1) == rolhash.substr(l2, len2); assert(equality_rangeHash == equality_expected); assert(equality_substr == equality_expected); } } } errln("OK"); } void test_concat() { vector<int> a{1, 2, 3, 1, 2, 3}; RH rolhash(all(a)); const auto N = a.size(); rep(l, 0, N) rep(m, l + 1, N) rep(r, m + 1, N) { const auto leftHash = rolhash.rangeHash(l, m); const auto rightHash = rolhash.rangeHash(m, r); const auto got = rolhash.concat(leftHash, rightHash, r - m); const auto expected = rolhash.rangeHash(l, r); assert(got == expected); } errln("OK"); } int main() { std::cout << "Hello World" << std::endl; test_hash(); test_rangeHash_and_substr(); test_concat(); return 0; }
#line 1 "test/helloworld/rolling-hash.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #line 2 "String/rolling-hash.hpp" #line 7 "String/rolling-hash.hpp" /** * @brief Rolling-Hash (ローリングハッシュ, mod値 $2^{61} - 1$ 固定) * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 */ template <uint_fast64_t Base> class RollingHash { public: using u64 = uint_fast64_t; using u128 = __uint128_t; static constexpr u64 MOD = (1uL << 61) - 1; static constexpr u64 BASE = Base; private: std::vector<u64> m_hash; public: RollingHash() = default; template <class InputIter> RollingHash(InputIter begin, InputIter end) : m_hash(std::distance(begin, end) + 1, 0) { if (powArray().empty()) { powArray().reserve(1e6); powArray().emplace_back(1); } growPowArray(m_hash.size()); size_t i; InputIter itr; for (itr = begin, i = 0; itr != end; ++itr, ++i) { m_hash[i + 1] = add(mul(m_hash[i], BASE), *itr); } } //! 文字列全体のハッシュ値 u64 hash() const { return m_hash.back(); } //! 半開区間 [l, r) のハッシュ値 u64 rangeHash(size_t l, size_t r) const { assert(l < r && r < m_hash.size()); return add(m_hash[r], MOD - mul(m_hash[l], powArray()[r - l])); } //! rangeHash(begin, begin + length) と等価 u64 substr(size_t begin, size_t length) const { return rangeHash(begin, begin + length); } //! もとの文字列の長さ size_t size() const { return m_hash.size() - 1; } //! 連結した文字列 (leftStr + rightStr) のハッシュ値 static u64 concat(u64 leftHash, u64 rightHash, size_t rightLength) { growPowArray(rightLength); return add(mul(leftHash, powArray()[rightLength]), rightHash); } private: static inline std::vector<u64>& powArray() { static std::vector<u64> p; return p; } static constexpr inline u64 add(u64 a, u64 b) noexcept { if ((a += b) >= MOD) a -= MOD; return a; } static constexpr inline u64 mul(u128 a, u128 b) noexcept { const auto c = a * b; return add(static_cast<u64>(c >> 61), static_cast<u64>(c & MOD)); } static inline void growPowArray(size_t len) { ++len; while (powArray().size() < len) { powArray().emplace_back(mul(powArray().back(), BASE)); } } }; #line 5 "test/helloworld/rolling-hash.test.cpp" #line 2 "Util/randoms.hpp" #line 5 "Util/randoms.hpp" /** * @brief randoms (randint()とかchoice()とか) */ namespace arumakan::random { std::mt19937 mt(std::random_device{}()); //! 閉区間[min, max] の乱数を一様分布で生成する template <class Integer> Integer randint(Integer min, Integer max) { return std::uniform_int_distribution<Integer>(min, max)(mt); } //! dest に randint(sizeMin, sizeMax) 回 randint(valueMin, valueMax) を格納する template <class OutputIter, class Integer> OutputIter randomValueContainer(OutputIter dest, Integer valueMin, Integer valueMax, size_t sizeMin, size_t sizeMax) { auto size = randint(sizeMin, sizeMax); while (size--) { *dest = randint(valueMin, valueMax); ++dest; } return dest; } //! 要素数が randint(sizeMin, sizeMax) の randint(valueMin, valueMax) を生成する template <class Container, class Integer> Container randomValueContainer(Integer valueMin, Integer valueMax, size_t sizeMin, size_t sizeMax) { Container ret; randomValueContainer(std::back_inserter(ret), valueMin, valueMax, sizeMin, sizeMax); return ret; } //! [begin, end) の範囲のうちひとつをランダムに選んで返す template <class RandomAccessIter> auto choice(RandomAccessIter begin, RandomAccessIter end) { const auto i = randint<size_t>(0, std::distance(begin, end)); return begin[i]; } } // namespace rand #line 2 "Util/all-macro.hpp" /** * @brief all()マクロ */ #define all(x) std::begin(x), std::end(x) #define rall(x) std::rbegin(x), std::rend(x) #line 2 "Util/rep-macro.hpp" /** * @brief rep()マクロ */ #define rep(i, begin, end) for (int64_t i = (begin), i##_end = (end); i < i##_end; ++i) #define repc(i, begin, last) for (int64_t i = (begin), i##_last = (last); i <= i##_last; ++i) #define repr(i, begin, last) for (int64_t i = (begin), i##_last = (last); i >= i##_last; --i) #line 2 "Util/Debug/errln.hpp" #line 4 "Util/Debug/errln.hpp" /** * @brief errln() (println()のstderr版, デバッグ時のみ有効) */ inline void eprintln() { std::clog << std::endl; } template <class Head, class... Tail> inline void eprintln(Head&& head, Tail&&... tail) { std::clog << head << &" "[!sizeof...(tail)]; eprintln(std::forward<Tail>(tail)...); } #ifdef LOCAL_DEBUG #define errln(...) std::clog << __FILE__ << "(" << __LINE__ << ")[" << __func__ << "()]: ", eprintln(__VA_ARGS__) #else #define errln(...) ((void)0) #endif #line 10 "test/helloworld/rolling-hash.test.cpp" using namespace std; namespace rnd = arumakan::random; using RH = RollingHash<17273747>; const auto testdatas = []() -> vector<pair<string, RH>> { string s1 = "a"; string s2 = "zzzzz"; string s3 = rnd::randomValueContainer<string>('a', 'b', 30, 50); string s4 = rnd::randomValueContainer<string>('x', 'z', 30, 50); return { {s1, RH(all(s1))}, {s2, RH(all(s2))}, {s3, RH(all(s3))}, {s4, RH(all(s4))}, }; }(); void test_hash() { for (const auto& [str, rolhash] : testdatas) { assert(rolhash.hash() == rolhash.rangeHash(0, str.length())); } errln("OK"); } void test_rangeHash_and_substr() { for (const auto& [str, rolhash] : testdatas) { const auto N = str.length(); rep(l1, 0, N) rep(r1, l1 + 1, N) { rep(l2, 0, N) rep(r2, l2 + 1, N) { const auto len1 = r1 - l1; const auto len2 = r2 - l2; const bool equality_expected = string_view(str).substr(l1, len1) == string_view(str).substr(l2, len2); const bool equality_rangeHash = rolhash.rangeHash(l1, r1) == rolhash.rangeHash(l2, r2); const bool equality_substr = rolhash.substr(l1, len1) == rolhash.substr(l2, len2); assert(equality_rangeHash == equality_expected); assert(equality_substr == equality_expected); } } } errln("OK"); } void test_concat() { vector<int> a{1, 2, 3, 1, 2, 3}; RH rolhash(all(a)); const auto N = a.size(); rep(l, 0, N) rep(m, l + 1, N) rep(r, m + 1, N) { const auto leftHash = rolhash.rangeHash(l, m); const auto rightHash = rolhash.rangeHash(m, r); const auto got = rolhash.concat(leftHash, rightHash, r - m); const auto expected = rolhash.rangeHash(l, r); assert(got == expected); } errln("OK"); } int main() { std::cout << "Hello World" << std::endl; test_hash(); test_rangeHash_and_substr(); test_concat(); return 0; }