This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
#define MAXLEN 1000010
constexpr uint64_t Hmod= (1ULL << 61) - 1;
const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (Hmod / 3) + (Hmod / 3);
uint64_t base_pow[MAXLEN];
int64_t modmul(uint64_t a, uint64_t b){
uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & Hmod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & Hmod) + (ret >> 61);
ret = (ret & Hmod) + (ret >> 61);
return ret - 1;
}
void init(){
base_pow[0] = 1;
for (int i = 1; i < MAXLEN; i++){
base_pow[i] = modmul(base_pow[i - 1], base);
}
}
struct PolyHash{
vector<int64_t> pref, suff;
PolyHash() {}
template <typename T>
PolyHash(const vector<T>& ar){
if (!base_pow[0]) init();
int n = ar.size();
assert(n < MAXLEN);
pref.resize(n + 3, 0), suff.resize(n + 3, 0);
for (int i = 1; i <= n; i++){
pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
if (pref[i] >= Hmod) pref[i] -= Hmod;
}
for (int i = n; i >= 1; i--){
suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
if (suff[i] >= Hmod) suff[i] -= Hmod;
}
}
PolyHash(const char* str)
: PolyHash(vector<char> (str, str + strlen(str))) {}
uint64_t get_hash(int l, int r){
int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
return h < 0 ? h + Hmod : h;
}
uint64_t rev_hash(int l, int r){
int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
return h < 0 ? h + Hmod : h;
}
};
PolyHash PolyH(string s){
vector<char>v;
for(auto &i:s)v.push_back(i);
return PolyHash(v);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string s;
cin>>s;
PolyHash h=PolyH(s);
int ans=0,cnt=0,n=s.size();
map<int,vector<pair<int,int>>>mp;
map<int,pair<int,int>>mop;
for(int i=0;i<n;i++){
cnt++;
if(i==n-1||s[i]!=s[i+1]){
for(int w=0;w<cnt;w++){
mop[h.get_hash(i-w,i)].first=w+1;
mop[h.get_hash(i-w,i)].second+=cnt-w;
}
if(mp[s[i]].size()&&mp[s[i]].back().second>=cnt&&h.get_hash(mp[s[i]].back().first,i-cnt)==h.rev_hash(mp[s[i]].back().first,i-cnt)){
mop[h.get_hash(mp[s[i]].back().first,i-cnt)].first=i-cnt-mp[s[i]].back().first+1+cnt*2;
mop[h.get_hash(mp[s[i]].back().first,i-cnt)].second++;
}
mp[s[i]].push_back({i+1,cnt});
cnt=0;
}
}
for(auto &i:mop)ans=max(ans,i.second.second*i.second.first);
for(int i=0;i<n;i++){
int l=i,r=n-i-1,mid,f=-1;
while(l<=r){
mid=(l+r)/2;
if(h.get_hash(i,i+mid)==h.rev_hash(i-mid,i)){f=mid;l=mid+1;}
else r=mid-1;
}
if(f==-1)continue;
ans=max(ans,f*2+1);
}
for(int i=1;i<n;i++){
int l=i,r=n-i-1,mid,f=-1;
while(l<=r){
mid=(l+r)/2;
if(h.get_hash(i,i+mid)==h.rev_hash(i-1-mid,i-1)){f=mid;l=mid+1;}
else r=mid-1;
}
if(f==-1)continue;
ans=max(ans,f*2+2);
}
cout<<ans;
}
Compilation message (stderr)
palindrome.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindrome.cpp:48:57: required from here
palindrome.cpp:39:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
39 | if (pref[i] >= Hmod) pref[i] -= Hmod;
palindrome.cpp:44:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
44 | if (suff[i] >= Hmod) suff[i] -= Hmod;
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |