test/aoj_ALDS1_14_B_l61m1.test.cpp

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

#include <cstdio>
#include <chrono>
#include <random>
#include <string>

#include "String/rolling_hash_l61m1.cpp"

int main() {
  char buf[1048576];
  scanf("%s", buf);
  std::string t = buf;
  scanf("%s", buf);
  std::string p = buf;

  std::seed_seq ss{
    static_cast<uintmax_t>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()),
    static_cast<uintmax_t>(__builtin_ia32_rdtsc()),
  };
  std::mt19937 rng(ss);
  uintmax_t base = std::uniform_int_distribution<uintmax_t>(0, rolling_hash_l61m1::mod-1)(rng);

  uintmax_t crit = rolling_hash_l61m1(p.begin(), p.end(), base).substr(0);
  rolling_hash_l61m1 rt(t.begin(), t.end(), base);
  for (size_t i = 0; i + p.length() <= t.length(); ++i) {
    if (rt.substr(i, p.length()) == crit)
      printf("%zu\n", i);
  }
}

#line 1 "test/aoj_ALDS1_14_B_l61m1.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <cstdio>
#include <chrono>
#include <random>
#include <string>

#line 1 "String/rolling_hash_l61m1.cpp"



/**
 * @brief mod 2^61-1 のローリングハッシュ
 * @author えびちゃん
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 */

#include <cstddef>
#include <cstdint>
#include <vector>

#line 1 "utility/literals.cpp"



/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#line 11 "utility/literals.cpp"

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

constexpr int8_t   operator ""_i8(unsigned long long n)  { return n; }
constexpr int16_t  operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t  operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t  operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t  operator ""_u8(unsigned long long n)  { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }


#line 15 "String/rolling_hash_l61m1.cpp"

class rolling_hash_l61m1 {
public:
  using size_type = size_t;
  using value_type = uintmax_t;
  static value_type const mod = (1_ju << 61) - 1;
  static size_type const npos = -1;

private:
  value_type M_b;
  std::vector<value_type> M_c, M_p;

  static value_type S_fma(value_type a, value_type b, value_type c) {
    value_type au = a >> 31;
    value_type al = a & ((1u << 31) - 1);
    value_type bu = b >> 31;
    value_type bl = b & ((1u << 31) - 1);

    value_type x = au*bl + al*bu;
    value_type xu = x >> 30;
    value_type xl = x & ((1u << 30) - 1);

    value_type y = ((au*bu) << 1) + (xu + (xl << 31)) + (al*bl);
    value_type yu = y >> 61;
    value_type yl = y & ((1_ju << 61) - 1);

    value_type z = yu + yl + c;
    if (z >= mod) z -= mod;
    return z;
  }

  void M_build() {
    for (size_type i = 1; i < M_c.size(); ++i)
      M_c[i] = S_fma(M_c[i-1], M_b, M_c[i]);
    M_c.insert(M_c.begin(), 0);

    M_p.assign(M_c.size(), 1);
    for (size_type i = 1; i < M_p.size(); ++i)
      M_p[i] = S_fma(M_p[i-1], M_b, 0);
  }

public:
  rolling_hash_l61m1() = default;

  template <typename InputIt>
  rolling_hash_l61m1(InputIt first, InputIt last, value_type base): M_b(base) {
    assign(first, last);
  }

  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    M_c.assign(first, last);
    M_build();
  }

  template <typename InputIt>
  void assign(InputIt first, InputIt last, value_type base) {
    M_b = base;
    M_c.assign(first, last);
    M_build();
  }

  value_type substr(size_type pos, size_type len = npos) {
    size_type n = M_c.size() - 1;
    if (len == npos) len = n - pos;
    size_type endpos = pos + len;
    value_type hr = M_c[endpos];
    value_type hl = M_c[pos];
    value_type hs = hr - S_fma(hl, M_p[len], 0);
    if (hs >= mod)  // "negative"
      hs += mod;
    return hs;
  }
};


#line 9 "test/aoj_ALDS1_14_B_l61m1.test.cpp"

int main() {
  char buf[1048576];
  scanf("%s", buf);
  std::string t = buf;
  scanf("%s", buf);
  std::string p = buf;

  std::seed_seq ss{
    static_cast<uintmax_t>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()),
    static_cast<uintmax_t>(__builtin_ia32_rdtsc()),
  };
  std::mt19937 rng(ss);
  uintmax_t base = std::uniform_int_distribution<uintmax_t>(0, rolling_hash_l61m1::mod-1)(rng);

  uintmax_t crit = rolling_hash_l61m1(p.begin(), p.end(), base).substr(0);
  rolling_hash_l61m1 rt(t.begin(), t.end(), base);
  for (size_t i = 0; i + p.length() <= t.length(); ++i) {
    if (rt.substr(i, p.length()) == crit)
      printf("%zu\n", i);
  }
}