Submission #997453

#TimeUsernameProblemLanguageResultExecution timeMemory
997453vjudge1Palindromes (APIO14_palindrome)C++17
23 / 100
1040 ms5608 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod[2] = {ll(1e9 + 7), ll(1e9 + 9)}; const ll base[2] = {ll(727), ll(1e6 + 1)}; const ll N = 3e5 + 10; string s; ll n, base_pwr[2][N], inv[2]; ll pwr(ll a, ll b, ll id){ if (b < 0) return 0; if (b == 0) return 1; ll val = pwr(a, b / 2, id); val *= val; val %= mod[id]; if (b % 2) val *= a; return val % mod[id]; } int main(){ for (ll j = 0; j < 2; j ++){ base_pwr[j][0] = 1; inv[j] = pwr(base[j], mod[j] - 2, j); for (ll i = 1; i < N; i ++) base_pwr[j][i] = base_pwr[j][i - 1] * base[j] % mod[j]; } cin >> s; n = s.size(); ll ans = 0; for (ll len = 1; len <= n; len ++){ ll hsh0[2] = {0}, hsh[2] = {0}; unordered_map<ll, ll> cnt; ll mx_occur = 0; for (ll i = 0; i < len; i ++){ for (ll j = 0; j < 2; j ++){ hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j]; hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j]; } } if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){ cnt[hsh[0]]++; mx_occur = 1; } for (ll i = 1; i + len - 1 < n; i ++){ for (ll j = 0; j < 2; j ++){ hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j]; hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j]; hsh[j] = (hsh[j] + mod[j]) % mod[j]; hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; hsh0[j] = (hsh0[j] * inv[j]) % mod[j]; hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j]; } if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){ cnt[hsh[0]]++; mx_occur = max(mx_occur, cnt[hsh[0]]); } } ans = max(ans, len * mx_occur); } cout << ans << endl; }
#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...