제출 #971495

#제출 시각아이디문제언어결과실행 시간메모리
971495kilkuwu회문 (APIO14_palindrome)C++17
47 / 100
1044 ms48880 KiB
#include <bits/stdc++.h> #define nl '\n' #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif int random_base(int lb, int rb) { bool deterministic = false; assert(rb - lb >= 2); int64_t seed = deterministic ? 1 : std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::mt19937_64 rng(seed); auto uid = std::uniform_int_distribution<long long>(lb + 1, rb - 1); int base = uid(rng); return base - (base % 2 == 0); } using HashType = std::pair<int, uint64_t>; constexpr int h_mod = 1e9 + 123; const int h_max_value = 1024; int h_base = random_base(h_max_value, h_mod - 1); std::vector<HashType> h_power = {{1, 1}}; void generate_power(int size) { while ((int)h_power.size() < size) { h_power.emplace_back((int64_t)h_power.back().first * h_base % h_mod, h_power.back().second * h_base); } } struct PolynomialHash { std::vector<HashType> hval; PolynomialHash() {} // Assuming that s[i] > 0 PolynomialHash(const std::string& s) : hval(s.size() + 1) { generate_power(s.size() + 1); for (int i = 0; i < (int) s.size(); i++) { hval[i + 1].first = ((int64_t) hval[i].first * h_base + s[i]) % h_mod; hval[i + 1].second = hval[i].second * h_base + s[i]; } } // Assuming that s[i] > 0 PolynomialHash(const std::vector<int>& s) : hval(s.size() + 1) { generate_power(s.size() + 1); for (int i = 0; i < (int) s.size(); i++) { hval[i + 1].first = ((int64_t) hval[i].first * h_base + s[i]) % h_mod; hval[i + 1].second = hval[i].second * h_base + s[i]; } } // Get hash of range [l, r) HashType get(int l, int r) { int r1 = ((int64_t)hval[r].first - (int64_t)hval[l].first * h_power[r - l].first) % h_mod; uint64_t r2 = hval[r].second - hval[l].second * h_power[r - l].second; return {r1 + (r1 < 0) * h_mod, r2}; } }; struct ReversePolynomialHash { std::vector<HashType> hval; ReversePolynomialHash() {} // Assuming that s[i] > 0 ReversePolynomialHash(const std::string& s) : hval(s.size() + 1) { generate_power(s.size() + 1); for (int i = 0; i < (int) s.size(); i++) { int j = s.size() - i - 1; hval[i + 1].first = ((int64_t) hval[i].first * h_base + s[j]) % h_mod; hval[i + 1].second = hval[i].second * h_base + s[j]; } } // Assuming that s[i] > 0 ReversePolynomialHash(const std::vector<int>& s) : hval(s.size() + 1) { generate_power(s.size() + 1); for (int i = 0; i < (int) s.size(); i++) { int j = s.size() - i - 1; hval[i + 1].first = ((int64_t) hval[i].first * h_base + s[j]) % h_mod; hval[i + 1].second = hval[i].second * h_base + s[j]; } } // Get reverse hash of range [l, r) HashType get(int l, int r) { l = hval.size() - l - 1; r = hval.size() - r - 1; std::swap(l, r); int r1 = ((int64_t)hval[r].first - (int64_t)hval[l].first * h_power[r - l].first) % h_mod; uint64_t r2 = hval[r].second - hval[l].second * h_power[r - l].second; return {r1 + (r1 < 0) * h_mod, r2}; } }; const int mxN = 3e5 + 1; std::map<HashType, int> mp[mxN]; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string s; std::cin >> s; int n = s.size(); PolynomialHash h1(s); ReversePolynomialHash h1r(s); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { auto hf = h1.get(i, j + 1); auto hr = h1r.get(i, j + 1); if (hf == hr) { mp[j - i + 1][hf]++; } } } int64_t ans = 0; for (int len = 1; len <= n; len++) { for (auto [hv, cnt] : mp[len]) { ans = std::max(ans, (int64_t) cnt * len); } } std::cout << ans << nl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...