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/library-checker/zalgorithm/fast-rolling-hash-lcp.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/zalgorithm

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/cpp-template/header/vector-ios.hpp"
#include "src/sequence/fast-rolling-hash.hpp"

#include <iostream>
#include <string>
#include <vector>

namespace luz {

  void main_() {
    std::string s;
    std::cin >> s;

    const usize n = s.size();

    FastRollingHash froll;
    const auto hs = froll.build(s.begin(), s.end());

    std::vector< usize > ans;
    for (usize i: rep(0, n)) {
      ans.emplace_back(froll.lcp(hs, 0, n, hs, i, n));
    }

    std::cout << ans << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/library-checker/zalgorithm/fast-rolling-hash-lcp.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/zalgorithm

#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 2 "src/cpp-template/header/vector-ios.hpp"

#line 4 "src/cpp-template/header/vector-ios.hpp"

#include <iostream>
#include <vector>

namespace luz {

  template < typename T >
  std::ostream &operator<<(std::ostream &os,
                           const std::vector< T > vs) {
    for (usize i: rep(0, vs.size())) {
      os << vs[i] << (i + 1 != vs.size() ? " " : "");
    }
    return os;
  }

  template < typename T >
  std::istream &operator>>(std::istream &is, std::vector< T > &vs) {
    for (T &v: vs) {
      is >> v;
    }
    return is;
  }

} // namespace luz
#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 6 "src/sequence/fast-rolling-hash.hpp"

#line 8 "src/sequence/fast-rolling-hash.hpp"
#include <cassert>
#include <chrono>
#include <random>
#line 12 "src/sequence/fast-rolling-hash.hpp"

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 7 "test/library-checker/zalgorithm/fast-rolling-hash-lcp.test.cpp"

#line 9 "test/library-checker/zalgorithm/fast-rolling-hash-lcp.test.cpp"
#include <string>
#line 11 "test/library-checker/zalgorithm/fast-rolling-hash-lcp.test.cpp"

namespace luz {

  void main_() {
    std::string s;
    std::cin >> s;

    const usize n = s.size();

    FastRollingHash froll;
    const auto hs = froll.build(s.begin(), s.end());

    std::vector< usize > ans;
    for (usize i: rep(0, n)) {
      ans.emplace_back(froll.lcp(hs, 0, n, hs, i, n));
    }

    std::cout << ans << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page