library

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

View the Project on GitHub Harui-i/library

:heavy_check_mark: test/verify/aoj-alds-1-14-b.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#include "template/template.hpp"

#include <string>

#include "string/rolling-hash.hpp"


int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string T, P;
  cin >> T >> P;

  using mint = modint2611;
  mint base = mint::generate_base();

  RollingHash rlh_t(T,base);
  RollingHash rlh_p(P,base);
  Hash b = rlh_p.get(0, int(P.size()));

  for (int i=0; i+int(P.size()) <= int(T.size()); i++) {
    Hash a = rlh_t.get(i, i+int(P.size()));
    if (a == b) {
      cout << i << endl;
    }
  }
  return 0;
}
#line 1 "test/verify/aoj-alds-1-14-b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 3 "test/verify/aoj-alds-1-14-b.test.cpp"

#include <string>

#line 1 "string/rolling-hash.hpp"



#line 5 "string/rolling-hash.hpp"
#include <vector>
#line 7 "string/rolling-hash.hpp"

#line 1 "math/modint2611.hpp"



#include <random>
#include <chrono>
/*
法が2^61 - 1のmodint
cf: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 */

struct modint2611 {

  constexpr static const uint64_t mod = (1ull << 61ull) - 1;
  using uint128_t = __uint128_t;
  uint64_t _val;

  constexpr explicit modint2611() : _val(0) {}

  constexpr explicit modint2611(uint64_t v) : _val(v) {
    if (_val >= mod) _val -= mod;
  }

  constexpr modint2611& operator+=(const modint2611& rhs) {
    if ((_val += rhs._val) >= mod) _val -= mod;
    return *this;
  }

  constexpr modint2611& operator-=(const modint2611& rhs) {
    if (_val < rhs._val) {
      _val += (mod - rhs._val);
    }
    else {
      _val += -rhs._val;
    }
    return *this;
  }

  constexpr modint2611& operator*=(const modint2611& rhs) {
    uint128_t c = (uint128_t) _val * rhs._val;
    // return (c>>61) + (c & mod);
    uint64_t d = (c>>61) + (c & mod);
    if (d >= mod) d -= mod;

    _val = d;
    return *this;
  }
  
  constexpr modint2611 operator-() const { return modint2611(0) - *this; }

  constexpr modint2611 operator+(const modint2611& a) const {
    return modint2611(*this) += a;
  }

  constexpr modint2611 operator-(const modint2611& a) const {
    return modint2611(*this) -= a;
  }

  constexpr modint2611 operator*(const modint2611& a) const {
    return modint2611(*this) *= a;
  }
  
  constexpr bool operator==(const modint2611& a) const { return _val == a._val; }

  constexpr bool operator!=(const modint2611& a) const { return _val != a._val; }

  constexpr uint64_t val() const {
    return _val;
  }

  constexpr modint2611 pow(uint64_t n) const {
    modint2611 ret = modint2611(1);
    modint2611 base = *this;
    while (n) {
      if (n & 1) ret *= base;
      base *= base;
      n >>= 1;
    }
    return ret;
  }

  constexpr modint2611 inv() const {
    return (*this).pow(mod - 2);
  }

  static inline modint2611 generate_base() {
    mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution< uint64_t > rand(1, mod - 1);

    return modint2611(rand(mt));
  }

};


#line 9 "string/rolling-hash.hpp"

struct Hash {
  using mint = modint2611;
  mint hash;
  mint base;
  int len;

  // コンストラクタ
  constexpr Hash(mint _hash, mint _base, int _len): hash(_hash), base(_base), len(_len) {
  }

  // 文字列sのハッシュを返す
  constexpr Hash(std::string s, mint _base): hash(mint(0)), base(_base) {
    hash = mint(0);
    base = _base;
    len = int(s.size());

    mint pow = mint(1);
    for (int i=0; i<int(s.size()); i++){
      hash += pow * mint(s[i]);
      pow *= base;
    }
  }

  // 文字cのハッシュを返す
  constexpr Hash(char c, mint _base): base(_base) {
    hash = mint(c) * base;
    len = 1;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const Hash& rhs) {
    assert(base == rhs.base);
    hash += base.pow(len) * rhs.hash;
    len += rhs.len;
    return *this;
  }

  // 文字列としての結合をしたあとのHashを返す
  constexpr Hash& operator+=(const char& c) {
    hash += base.pow(len) * mint(c);
    len++;
    return *this;
  }

  constexpr Hash operator+(const Hash& rhs) const {
    return Hash(*this) += rhs; 
  }

  constexpr Hash operator+(const char& c) const {
    return Hash(*this) + c;
  }

  constexpr bool operator==(const Hash& rhs) const {
    return len == rhs.len && hash == rhs.hash;
  }

  bool operator<(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() < rhs.hash.val()) return true;
    if (hash.val() > rhs.hash.val()) return false;
    return len < rhs.len;
  }

  bool operator>(const Hash& rhs) const {
    assert(base == rhs.base);
    if (hash.val() > rhs.hash.val()) return false;
    if (hash.val() < rhs.hash.val()) return true;
    return len > rhs.len;
  }

  friend std::ostream& operator<<(std::ostream& os, const Hash& hash) {
    os << "Hash{len: ";
    os << hash.len;
    os << ", hash: ";
    os << hash.hash.val();
    os << ", base: ";
    os << hash.base.val();
    os << "}";
    return os;
  }
};

struct RollingHash {
  using mint = modint2611;
  std::vector<mint> hashes;
  mint base;
  constexpr RollingHash (const std::string& S, mint _base) : base(_base) {
    int N = int(S.size());
    hashes.resize(N+1);
    mint powb = base;
    for (int i=0; i<N; i++) {
      hashes[i+1] = hashes[i] + powb * mint(S[i]);
      powb *= base;
    }
  }

  constexpr Hash get(int l, int r) const {
    assert(0 <= l && l <= r && r < int(hashes.size()));
    mint hash_val = (hashes[r] - hashes[l])*(base.pow(l).inv());
    return Hash(hash_val, base, r-l);
  }

};



#line 7 "test/verify/aoj-alds-1-14-b.test.cpp"


int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string T, P;
  cin >> T >> P;

  using mint = modint2611;
  mint base = mint::generate_base();

  RollingHash rlh_t(T,base);
  RollingHash rlh_p(P,base);
  Hash b = rlh_p.get(0, int(P.size()));

  for (int i=0; i+int(P.size()) <= int(T.size()); i++) {
    Hash a = rlh_t.get(i, i+int(P.size()));
    if (a == b) {
      cout << i << endl;
    }
  }
  return 0;
}
Back to top page