test/string/RollingHash.test.cpp

View this file on GitHub
Last update: 2024-05-31 19:00:40+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include "test/template.hpp"
using u64 = uint64_t;
#include "src/string/RollingHash.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   RH rh(S);
   const ll N = sz(S);
   auto LCP = [&](ll i, ll j) {
      ll ok = 0, ng = N + 1 - j;
      while(ng - ok > 1) {
         const ll mid = (ok + ng) / 2;
         (rh.get(i, i + mid) == rh.get(j, j + mid) ? ok : ng) = mid;
      }
      return ok;
   };
   rep(i, 0, N) cout << LCP(0, i) << " \n"[i + 1 == N];
}

#line 1 "test/string/RollingHash.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 3 "test/string/RollingHash.test.cpp"
using u64 = uint64_t;
#line 1 "src/string/RollingHash.hpp"
// using u64 = uint64_t;
const u64 mod = INF;
u64 add(u64 a, u64 b) {
   a += b;
   if(a >= mod) a -= mod;
   return a;
}
u64 mul(u64 a, u64 b) {
   auto c = (__uint128_t)a * b;
   return add(c >> 61, c & mod);
}
random_device rnd;
const u64 r = ((u64)rnd() << 32 | rnd()) % mod;
struct RH {
   ll n;
   vector<u64> hs, pw;
   RH(string s) : n(sz(s)), hs(n + 1), pw(n + 1, 1) {
      rep(i, 0, n) {
         pw[i + 1] = mul(pw[i], r);
         hs[i + 1] = add(mul(hs[i], r), s[i]);
      }
   }
   u64 get(ll l, ll r) const { return add(hs[r], mod - mul(hs[l], pw[r - l])); }
};
#line 5 "test/string/RollingHash.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   RH rh(S);
   const ll N = sz(S);
   auto LCP = [&](ll i, ll j) {
      ll ok = 0, ng = N + 1 - j;
      while(ng - ok > 1) {
         const ll mid = (ok + ng) / 2;
         (rh.get(i, i + mid) == rh.get(j, j + mid) ? ok : ng) = mid;
      }
      return ok;
   };
   rep(i, 0, N) cout << LCP(0, i) << " \n"[i + 1 == N];
}