/*
! Bismillahirrahmanirrahim
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
/*
m : 11059739 -> l ~23
p : 4567896467
*/
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, sze = 1e6 + 50, inf = LLONG_MAX, prime = 17;
//\\
!!! dp ?recrusive? / binary search / greedy / sprase table / segment tree
//
int poly[sze];
int p[sze];
int n;
int qry2(int l,int r,int lx,int rx){
lx=n + (n - lx -1);
rx=n + (n - rx -1);
swap(lx,rx);
// cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
if(min({l,r,lx,rx})<0 || max({l,r,lx,rx})>n*2-1){
// cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
return 0;
}
int a = ( p[lx] * 1LL * ( (poly[r+1] - poly[l]) % mod) + mod ) % mod;
int b = ( p[l] * 1LL * ( (poly[rx+1] - poly[lx]) % mod) + mod ) % mod;
return (a==b);
}
int ps(str s){
memset(poly,0,sizeof poly);
str t=s;
reverse(all(t));
s+=t; // lmao
for(int i=1;i<=n+n;i++){
poly[i] = ( poly[i-1] + ((s[i-1]-'a'+1)* 1LL * p[i]) % mod + mod)%mod;
}
// cout<<s<<endl;
/*
ab ba
01 23
*/
// cout<<qry(1,1,6,6)<<endl;
// cout<<qry2(0,1,3,4)<<endl;
int ans =n;
// odd
for(int i=0;i<n;i++){
if(i>0){
int l =0;
int r = min((n-i -1),i) ;
int mid = 0;
while(l<=r){
int m = (l+r)/2;
// cout<<i<<" => "<<m<<" :: "<<i-m<<" "<<i-1<<" - "<<i+1<<" "<<i+m<<endl;
if(qry2(i-m,i-1, i+1,i+m)){
l=m+1;
mid=m;
}
else{
r=m-1;
}
}
ans+=mid;
// cout<<i<<" odd "<<mid<<endl;
}
if(i+1<n){
if(s[i]==s[i+1]){
int mid=0;
int l =0;
int r = min(i, n - (i+1) -1 );
while(l<=r){
int m = (l+r)/2;
// cout<<m<<" :: "<<i-m<<" "<<i<<" - "<<i+1<<" "<<i+1+m<<endl;
if(qry2(i-m,i,i+1,i+1+m)){
mid=m;
l=m+1;
}
else{
r=m-1;
}
}
// cout<<i<<" even "<<mid<<endl;
ans+=mid+1;
}
}
}
return ans;
}
void gkd(){
str s;
cin>>s;
n=(s.size());
p[0]=1;
for(int i=1;i<=n*2;i++){
p[i]=(p[i-1]*prime )%mod;
}
// cout<<qry(1,1,6,6)<<endl;
int mx =0;
// drop(ps(s));
for(int i=0;i<n;i++){
char ch=s[i];
for(int j=0;j<26;j++){
s[i]=char('a'+j);
mx=max(mx,ps(s));
// cout<<s<<" "<<mx<<endl;
}
s[i]=ch;
}
drop(mx);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin>>tt;
while (tt--)gkd();
}
Compilation message
palinilap.cpp:22:1: warning: multi-line comment [-Wcomment]
22 | //\\
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
9772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1045 ms |
9820 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
12632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
