This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B #include "src/sequence/fast-rolling-hash.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include <iostream> #include <string> namespace luz { void main_() { std::string t, p; std::cin >> t >> p; const usize n = t.size(), m = p.size(); if (n < m) return; FastRollingHash froll; const auto hs1 = froll.build(t.begin(), t.end()); const auto hs2 = froll.build(p.begin(), p.end()); for (usize i: rep(0, n - m + 1)) { if (froll.query(hs1, i, i + m) != froll.query(hs2, 0, m)) { continue; } std::cout << i << std::endl; } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/alds1_14_b/fast-rolling-hash.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B #line 2 "src/sequence/fast-rolling-hash.hpp" #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 6 "src/sequence/fast-rolling-hash.hpp" #line 8 "src/sequence/fast-rolling-hash.hpp" #include <cassert> #include <chrono> #include <random> #include <vector> namespace luz { class FastRollingHash { static constexpr u64 mod = (1ull << 61ull) - 1; const u64 base; std::vector< u64 > power; static u64 add(u64 a, u64 b) { if ((a += b) >= mod) a -= mod; return a; } static u64 mul(u64 a, u64 b) { u128 c = u128(a) * b; return add(c >> 61, c & mod); } void expand(usize sz) { usize l = power.size(), r = sz + 1; if (r <= l) return; power.resize(r); for (usize i: rep(l, r)) { power[i] = mul(power[i - 1], base); } } public: using Hs = std::vector< u64 >; FastRollingHash(): base(generate_base()), power{1} {} explicit FastRollingHash(u64 base): base(base), power{1} {} template < class Iter > Hs build(Iter first, Iter last) const { Hs hs(1); hs.reserve(last - first + 1); while (first != last) { u64 h = add(mul(hs.back(), base), *first); hs.emplace_back(h); ++first; } return hs; } u64 query(const Hs &s, usize l, usize r) { assert(l <= r and r < s.size()); expand(r - l); return add(s[r], mod - mul(s[l], power[r - l])); } u64 combine(u64 h1, u64 h2, usize h2len) { expand(h2len); return add(mul(h1, power[h2len]), h2); } usize lcp(const Hs &a, usize l1, usize r1, const Hs &b, usize l2, usize r2) { assert(l1 <= r1 and r1 < a.size()); assert(l2 <= r2 and r2 < b.size()); usize len = std::min(r1 - l1, r2 - l2); usize low = 0, high = len + 1; while (high - low > 1) { usize mid = (low + high) / 2; if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) { low = mid; } else { high = mid; } } return low; } private: static u64 mod_pow(u64 b, u64 e) { u64 res{1}; while (e) { if (e & 1) { res = mul(res, b); } b = mul(b, b); e >>= 1; } return res; } static bool is_primitive_root(u64 b) { constexpr u64 ps[] = {2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321}; for (const auto &p: ps) { if (mod_pow(b, (mod - 1) / p) == 1) { return false; } } return true; } static u64 generate_base() { std::mt19937_64 mt(std::chrono::steady_clock::now() .time_since_epoch() .count()); std::uniform_int_distribution< u64 > rand(1e9, mod - 1); while (true) { u64 b = rand(mt); if (not is_primitive_root(b)) { continue; } return b; } } }; } // namespace luz #line 4 "test/aoj/alds1_14_b/fast-rolling-hash.test.cpp" #line 7 "test/aoj/alds1_14_b/fast-rolling-hash.test.cpp" #include <iostream> #include <string> namespace luz { void main_() { std::string t, p; std::cin >> t >> p; const usize n = t.size(), m = p.size(); if (n < m) return; FastRollingHash froll; const auto hs1 = froll.build(t.begin(), t.end()); const auto hs2 = froll.build(p.begin(), p.end()); for (usize i: rep(0, n - m + 1)) { if (froll.query(hs1, i, i + m) != froll.query(hs2, 0, m)) { continue; } std::cout << i << std::endl; } } } // namespace luz int main() { luz::main_(); }