test/string/RollingHash.test.cpp

• View this file on GitHub
• Last update: 2026-07-28 02:32:12+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Rolling Hash (src/string/RollingHash.hpp)
• test/template.hpp

Code

// competitive-verifier: 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"
// competitive-verifier: 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;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#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);
}
const u64 r = random_device{}();
struct RH {
   ll n;
   V<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];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	104 ms	12 MB
g++	all_same_01	AC	100 ms	12 MB
g++	all_same_02	AC	101 ms	12 MB
g++	all_same_03	AC	104 ms	12 MB
g++	all_same_04	AC	100 ms	12 MB
g++	binary_carry_00	AC	90 ms	12 MB
g++	binary_carry_01	AC	91 ms	12 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	example_02	AC	2 ms	4 MB
g++	example_03	AC	2 ms	4 MB
g++	fib_str_00	AC	93 ms	12 MB
g++	fib_str_01	AC	70 ms	10 MB
g++	fib_str_02	AC	65 ms	10 MB
g++	fib_str_03	AC	61 ms	9 MB
g++	fib_str_04	AC	93 ms	12 MB
g++	hack606_00	AC	2 ms	4 MB
g++	max_random_00	AC	90 ms	12 MB
g++	max_random_01	AC	92 ms	12 MB
g++	random_00	AC	70 ms	10 MB
g++	random_01	AC	86 ms	12 MB
g++	random_02	AC	10 ms	4 MB
g++	random_03	AC	77 ms	11 MB
g++	random_04	AC	49 ms	8 MB
g++	random_05	AC	57 ms	9 MB
g++	random_06	AC	82 ms	12 MB
g++	random_07	AC	18 ms	5 MB
g++	random_08	AC	47 ms	8 MB
g++	random_09	AC	19 ms	5 MB

Back to top page