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>
using namespace std;
typedef long long ll;
const int MAXN=3e5+5;
const ll MOD=1e9+9;
const ll P=257;
char c[MAXN];
ll h[MAXN], rh[MAXN];
ll pot[MAXN];
int n;
ll respf=0;
ll ghash(int ini, int fim) {
ll val=0;
if(ini<=fim) {
if(ini!=0) val=h[ini-1];
val*=pot[fim-ini+1]; val%=MOD;
val=h[fim]-val;
while(val<0) val+=MOD;
}
else {
if(ini!=n-1) val=rh[ini+1];
val*=pot[ini-fim+1]; val%=MOD;
val=rh[fim]-val;
while(val<0) val+=MOD;
}
return val;
}
ll testa(int k) {
if(k==0||k==n+1) return 0;
if(k<0||k>n) return -1;
int resp=0;
// printf("testing %d\n", k);
unordered_map<ll, int> mp;
for(int i=k-1; i<n; i++) {
int ind=i-k+1;
ll val=ghash(ind, i);
// printf(" %d: %lld %lld\n", i, val, ghash(i, ind));
if(val==ghash(i, ind)) {
mp[val]++;
resp=max(resp, mp[val]);
}
}
// printf(" testa %d >> %lld\n", k, k*(ll)resp);
return (ll)resp*k;
}
void precalc() {
pot[0]=1;
for(int i=1; i<=n; i++) pot[i]=(pot[i-1]*P)%MOD;
for(int i=0; i<n; i++) {
if(i!=0) h[i]=(h[i-1]*P)%MOD;
h[i]+=(c[i]-'a'); h[i]%=MOD;
}
for(int i=n-1; i>=0; i--) {
if(i!=n-1) rh[i]=(rh[i+1]*P)%MOD;
rh[i]+=(c[i]-'a'); rh[i]%=MOD;
}
}
int main() {
scanf(" %s", c); n=strlen(c);
precalc();
// for(int i=1; i<=n; i++) respf=max(respf, testa(i));
int opt=-1;
for(int i=n; i>0; i/=2) {
// printf("testa %d // %d\n", i, opt);
while(opt+i<=n&&(testa(opt+i-1)<=testa(opt+i)||testa(opt+i-1)<=testa(opt+i+1))) {
opt+=i;
}
}
// printf("opt %d\n", opt);
respf=max(respf, testa(opt-2));
respf=max(respf, testa(opt-1));
respf=max(respf, testa(opt));
respf=max(respf, testa(opt+1));
respf=max(respf, testa(opt+2));
printf("%lld\n", respf);
}
Compilation message (stderr)
palindrome.cpp: In function 'int main()':
palindrome.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", c); n=strlen(c);
~~~~~^~~~~~~~~~
# | 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... |