#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cerr if(dbg)cerr
using namespace std;
const int n0=1e5+123;
int n;
string s;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace Sol {
bool dbg=0;
ll mul[n0],add[n0],positive[n0][26],init;
namespace Hash {
const array<int,2> mod={(int)1e9+7,(int)1e9+9};
int base=uniform_int_distribution<int>(27,(int)1e9)(rng);
struct mint {
array<int,2> x;
mint(int val=0) {
x[0]=x[1]=val;
}
void operator *= (const mint &a) {
x[0]=(ll)x[0]*a.x[0]%mod[0];
x[1]=(ll)x[1]*a.x[1]%mod[1];
}
void operator += (const mint &a) {
x[0]+=a.x[0];if(x[0]>=mod[0]) x[0]-=mod[0];
x[1]+=a.x[1];if(x[1]>=mod[1]) x[1]-=mod[1];
}
void operator -= (const mint &a) {
x[0]-=a.x[0];if(x[0]<0) x[0]+=mod[0];
x[1]-=a.x[1];if(x[1]<0) x[1]+=mod[1];
}
mint operator * (const mint &a) {
mint res=*this;
res*=a;
return res;
}
mint operator + (const mint &a) {
mint res=*this;
res+=a;
return res;
}
mint operator - (const mint &a) {
mint res=*this;
res-=a;
return res;
}
bool operator == (const mint &a) {
return x[0]==a.x[0] && x[1]==a.x[1];
}
};
mint pref[n0],suf[n0],pw[n0];
void build() {
pw[0]=1;
for(int i=1; i<=n; i++) {
pw[i]=pw[i-1]*base;
pref[i]=pref[i-1]+pw[i]*(s[i-1]-'a'+1);
}
for(int i=n; i>=1; i--) {
suf[i]=suf[i+1]+pw[n-i+1]*(s[i-1]-'a'+1);
}
};
mint get(int l,int r) {
return pw[n-r]*(pref[r]-pref[l-1]);
}
mint get_rev(int l,int r) {
return pw[l-1]*(suf[l]-suf[r+1]);
}
void clear() {
for(int i=0; i<n0; i++) {
pref[i]=suf[i]=pw[i]=0;
}
};
}
bool pal(int l,int r,int l2,int r2) {
if(l<1 || l2<1 || r>n || r2>n) return 0;
return Hash::get(l,r)==Hash::get_rev(l2,r2);
}
int find(int L,int R) {
int l=-1,r=n;
while(l<r-1) {
int mid=l+r>>1;
if(pal(L-mid,L,R,R+mid)) l=mid;
else r=mid;
}
return l;
}
void add_inc(int l,int r,int x) {
//(x-l)+i
add[l]+=x-l,add[r+1]-=x-l;
mul[l]++,mul[r+1]--;
}
void add_dec(int l,int r,int x) {
//(x+l)-i
add[l]+=x+l,add[r+1]-=x+l;
mul[l]--,mul[r+1]++;
}
ll get(int pos) {
return add[pos]+mul[pos]*pos;
}
void process(int L,int R) {
int a=find(L,R);
init+=a+1;
int b=find(L-a-2,R+a+2);
cerr << "process(" << L << "," << R << ")={" << a << "," << b << "}\n";
if(L-a-1>=1 && R+a+1<=n) {
positive[L-a-1][s[R+a]-'a']+=1+(b+1);
positive[R+a+1][s[L-a-2]-'a']+=1+(b+1);
}
if(a>=0) {
cerr << "neg\n";
cerr << "inc: " << L-a << ' ' << L << ",start=" << -1 << '\n';
cerr << "dec: " << R << ' ' << R+a << ",start=" << -a-1 << '\n';
add_dec(L-a,L,-1);
add_inc(R,R+a,-a-1);
}
}
void clear() {
Hash::clear();
mem(mul,0),mem(add,0),mem(positive,0),init=0;
};
ll solve(bool _dbg) {
dbg=_dbg;
clear();
Hash::build();
for(int i=1; i<=n-1; i++) process(i,i+1);
for(int i=1; i<=n-2; i++) process(i,i+2);
init+=n;
ll ans=init;
cerr << "init=" << ans << '\n';
for(int i=1; i<=n; i++) {
add[i]+=add[i-1];
mul[i]+=mul[i-1];
ll diff=get(i);
ll cur=0;
for(int j=0; j<26; j++) {
cur=0;
if(s[i-1]-'a'!=j) cur+=diff;
cur+=positive[i][j];
ans=max(ans,init+cur);
}
}
cerr << "neg[1]=" << get(1) << '\n';
cerr << "positive[1][1]=" << positive[1][1] << '\n';
return ans;
};
}
namespace Slow {
bool dbg=0;
ll count(string x) {
ll res=0;
for(int i=0; i<SZ(x); i++) {
for(int j=i; j<SZ(x); j++) {
int ok=1;
for(int k=i; k<=j; k++) {
int t=j-(k-i);
if(x[k]!=x[t]) {
ok=0;
break;
}
}
if(ok) {
res++;
}
}
}
return res;
}
ll solve(bool _dbg) {
ll ans=0;
string ans_t;
for(int i=0; i<n; i++) {
string t=s;
for(int j=0; j<26; j++) {
t[i]=char('a'+j);
ll val=count(t);
if(ans<val) {
ans=val;
ans_t=t;
}
}
}
cerr << ans_t << '\n';
return ans;
}
}
namespace Gen {
uniform_int_distribution<int> _n(1,5),_c(0,5);
void gen() {
s="";
n=_n(rng);
for(int i=0; i<n; i++) s+=char('a'+_c(rng));
}
void output() {
cout << n << '\n';
cout << s << '\n';
};
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> s;
n=SZ(s);
//ll sol=Sol::solve(1);
//ll slow=Slow::solve(1);
//cout << sol << ' ' << slow;
cout << Sol::solve(0);
//int tc=100000;
//while(tc--) {
//Gen::gen();
//ll sol=Sol::solve(0),slow=Slow::solve(0);
//if(sol!=slow) {
//cout << "WA\n";
//Gen::output();
//cout << "expected=" << slow << ", output=" << sol << '\n';
//return 0;
//}
//}
//cout << "OK";
}
Compilation message
palinilap.cpp: In function 'int Sol::find(int, int)':
palinilap.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
24684 KB |
Output is correct |
| 2 |
Correct |
14 ms |
24684 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24684 KB |
Output is correct |
| 4 |
Correct |
14 ms |
24684 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24684 KB |
Output is correct |
| 2 |
Correct |
18 ms |
24684 KB |
Output is correct |
| 3 |
Correct |
22 ms |
24708 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24684 KB |
Output is correct |
| 5 |
Correct |
19 ms |
24684 KB |
Output is correct |
| 6 |
Correct |
20 ms |
24684 KB |
Output is correct |
| 7 |
Correct |
19 ms |
24684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
24916 KB |
Output is correct |
| 2 |
Correct |
118 ms |
24940 KB |
Output is correct |
| 3 |
Correct |
122 ms |
24940 KB |
Output is correct |
| 4 |
Correct |
178 ms |
25016 KB |
Output is correct |
| 5 |
Correct |
186 ms |
25068 KB |
Output is correct |
| 6 |
Correct |
166 ms |
24940 KB |
Output is correct |
| 7 |
Correct |
169 ms |
25068 KB |
Output is correct |
| 8 |
Correct |
92 ms |
24940 KB |
Output is correct |
| 9 |
Correct |
172 ms |
24940 KB |
Output is correct |
| 10 |
Correct |
177 ms |
25068 KB |
Output is correct |
| 11 |
Correct |
121 ms |
24940 KB |
Output is correct |
| 12 |
Correct |
176 ms |
24940 KB |
Output is correct |
| 13 |
Correct |
176 ms |
24940 KB |
Output is correct |
| 14 |
Correct |
167 ms |
24940 KB |
Output is correct |
| 15 |
Correct |
167 ms |
24940 KB |
Output is correct |
| 16 |
Correct |
140 ms |
25016 KB |
Output is correct |
| 17 |
Correct |
160 ms |
24940 KB |
Output is correct |
| 18 |
Correct |
168 ms |
24940 KB |
Output is correct |
| 19 |
Correct |
157 ms |
24940 KB |
Output is correct |
