comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/aoj/alds1_14_b/fast-rolling-hash.test.cpp

Depends on

Code

// 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_();
}
Back to top page