#line 1 "main.cpp" #ifdef LOCAL #include #else #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2") #include #define debug(...) ((void)0) #define postprocess(...) ((void)0) #endif #line 1 "library/string/rolling_hash.hpp" #include #include #include #line 2 "library/misc/xorshift.hpp" #include inline uint32_t xorshift32() { static uint32_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count(); x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } inline uint64_t xorshift64() { static uint64_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count(); x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } #line 6 "library/string/rolling_hash.hpp" namespace rolling_hash { constexpr uint64_t mod = (1ull << 61) - 1; constexpr uint64_t primitive_root = 37; inline uint64_t multiply(const __uint128_t& x, const __uint128_t& y) { // https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 __uint128_t t = x * y; t = (t >> 61) + (t & mod); if (t >= mod) return t - mod; return t; } inline uint64_t pow_primitive_root(uint64_t k) { uint64_t ret = 1; uint64_t mul = primitive_root; while (k > 0) { if (k & 1) ret = multiply(ret, mul); mul = multiply(mul, mul); k >>= 1; } return ret; } inline uint64_t choose_base() { while (true) { uint64_t k = xorshift64() % (mod - 1); if (std::gcd(k, mod - 1) != 1) continue; uint64_t rk = pow_primitive_root(k); if (rk >= mod / 2) return rk; } } const uint64_t base0 = choose_base(); const uint64_t base1 = choose_base(); inline uint64_t pow0(uint64_t k) { uint64_t ret = 1; uint64_t mul = base0; while (k > 0) { if (k & 1) ret = multiply(ret, mul); mul = multiply(mul, mul); k >>= 1; } return ret; } inline uint64_t pow1(uint64_t k) { uint64_t ret = 1; uint64_t mul = base1; while (k > 0) { if (k & 1) ret = multiply(ret, mul); mul = multiply(mul, mul); k >>= 1; } return ret; } const uint64_t base0_inv = pow0(mod - 2); const uint64_t base1_inv = pow1(mod - 2); struct hash { uint64_t length; uint64_t hash0; uint64_t hash1; bool operator==(const hash& rhs) const { return hash0 == rhs.hash0 && hash1 == rhs.hash1 && length == rhs.length; } friend hash operator+(const hash& lhs, const hash& rhs) { hash ret; ret.length = lhs.length + rhs.length; ret.hash0 = multiply(lhs.hash0, pow0(rhs.length)) + rhs.hash0; ret.hash1 = multiply(lhs.hash1, pow1(rhs.length)) + rhs.hash1; if (ret.hash0 >= mod) ret.hash0 -= mod; if (ret.hash1 >= mod) ret.hash1 -= mod; return ret; } }; } // namespace rolling_hash struct RollingHash { RollingHash(const std::string& s) : n(s.size()) { std::vector v(s.size()); for (int i = 0; i < (int)s.size(); i++) { v[i] = (uint64_t)s[i]; } init(v); } template RollingHash(const std::vector& s) : n(s.size()) { static_assert(std::is_integral_v, "T must be an integer type"); std::vector v(s.size()); for (int i = 0; i < (int)s.size(); i++) { v[i] = (uint64_t)s[i]; } init(v); } int size() { return n; } // returns hash value for [l, r). // Complexity: O(1) rolling_hash::hash query(int l, int r) { assert(0 <= l); assert(l <= r); assert(r <= n); rolling_hash::hash ret; if (r == 0) { ret.length = r; ret.hash0 = 0; ret.hash1 = 0; return ret; } if (l == 0) { ret.length = r; ret.hash0 = accumulated0[r - 1]; ret.hash1 = accumulated1[r - 1]; return ret; } ret.length = r - l; ret.hash0 = accumulated0[r - 1] - accumulated0[l - 1] + rolling_hash::mod; if (ret.hash0 >= rolling_hash::mod) ret.hash0 -= rolling_hash::mod; ret.hash0 = rolling_hash::multiply(ret.hash0, inv0[l]); ret.hash1 = accumulated1[r - 1] - accumulated1[l - 1] + rolling_hash::mod; if (ret.hash1 >= rolling_hash::mod) ret.hash1 -= rolling_hash::mod; ret.hash1 = rolling_hash::multiply(ret.hash1, inv1[l]); return ret; } // returns the length of Longest Common Prefix // between suffixes starting from l1, l2, // that is, maximum L such that [l1, l1 + L) == [l2, l2 + L). // Complexity: O(log N) int lcp(int l1, int l2) { int imin = 0; int imax = n - std::max(l1, l2) + 1; while (imax - imin > 1) { int imid = (imin + imax) / 2; auto h1 = query(l1, l1 + imid); auto h2 = query(l2, l2 + imid); (h1 == h2 ? imin : imax) = imid; } return imin; } private: int n; std::vector accumulated0; std::vector accumulated1; std::vector inv0; std::vector inv1; void init(const std::vector& v) { accumulated0.resize(n); accumulated1.resize(n); uint64_t base0 = 1; uint64_t base1 = 1; for (int i = 0; i < (int)v.size(); i++) { accumulated0[i] = rolling_hash::multiply(v[i], base0); accumulated1[i] = rolling_hash::multiply(v[i], base1); base0 = rolling_hash::multiply(base0, rolling_hash::base0); base1 = rolling_hash::multiply(base1, rolling_hash::base1); } for (int i = 1; i < (int)v.size(); i++) { accumulated0[i] += accumulated0[i - 1]; if (accumulated0[i] >= rolling_hash::mod) accumulated0[i] -= rolling_hash::mod; accumulated1[i] += accumulated1[i - 1]; if (accumulated1[i] >= rolling_hash::mod) accumulated1[i] -= rolling_hash::mod; } inv0.resize(n); inv1.resize(n); inv0[0] = 1; inv1[0] = 1; for (int i = 0; i + 1 < n; i++) { inv0[i + 1] = rolling_hash::multiply(inv0[i], rolling_hash::base0_inv); inv1[i + 1] = rolling_hash::multiply(inv1[i], rolling_hash::base1_inv); } } }; #line 12 "main.cpp" using namespace std; using ll = long long; using ld = long double; void solve([[maybe_unused]] int test) { string S; cin >> S; int N = S.size(); RollingHash rh(S); const auto pattern = RollingHash("yukicoder").query(0, 9); int imin = 0; int imax = 1000000; while (imax - imin > 1) { int imid = (imin + imax) / 2; auto hash = pattern; for (int i = 1; i < imid; i++) { hash = hash + pattern; } bool ok = false; int len = imid * 9; for (int i = 0; i + len <= N; i++) { if (rh.query(i, i + len) == hash) { ok = true; break; } } (ok ? imin : imax) = imid; } cout << imin << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(i); } postprocess(); }