#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define ld long double
#define f(i,a,b) for(int i=a;i<b;++i)
#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;
#define PQ priority_queue
#define LB lower_bound
#define UB upper_bound
#define fr first
#define sc second
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define show(a) {for(auto xyz:a)cout<<xyz<<" ";cout<<endl;}
#define sz(x) (int)(x).size()
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
/**
* Description: Polynomial hash for substrings with two bases.
* Source:
* BENQ, own modifications
* KACTL
* https://codeforces.com/contest/1207/submission/59309672
* Verification: https://codeforces.com/contest/835/submission/102412420
*/
#define int long long // this is imp
const int MOD = 1e9 + 9 ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> BDIST(0.1*MOD,0.9*MOD);
const array<int,2> base = {BDIST(rng), BDIST(rng)};
vector<array<int,2>> pows = {{1,1}};
struct HashRange {
string S;
vector< array<int,2> > cum = {{0,0}};
void add(char c) {
S += c;
cum.push_back( { (base[0] * cum.back()[0] + c )%MOD, (base[1] * cum.back()[1] + c )%MOD } );
}
void add(string s) {
for(auto c:s) add(c);
}
void extend(int len) {
while ((int)(pows.size()) <= len) {
pows.push_back({ (base[0] * pows.back()[0])%MOD, (base[1] * pows.back()[1])%MOD });
}
}
array<int,2> hash(int l, int r) { // 0 based indexing
int len = r+1-l; extend(len);
return { ((cum[r+1][0] - pows[len][0] * cum[l][0])%MOD + MOD)%MOD, ((cum[r+1][1] - pows[len][1] * cum[l][1])%MOD + MOD)%MOD };
}
};
const int N = 1e5 + 7 ;
int inc[N][26], A1[N], A2[N], B1[N], B2[N];
signed main(){
setIO();
string s; cin >> s ;
string rs = s ; reverse(all(rs)) ;
HashRange S, RS ; S.add(s) ; RS.add(rs) ;
int n = sz(s), actual = 0 ;
for(int i=0; i<n; ++i){
// solve for odd len
{
int lo = 1, hi = min(i+1, n-i) + 1 ;
while(hi-lo>1){
int mid = (hi+lo)/2 ;
int s1 = i, e1 = i + mid - 1 ;
int s2 = n - i - 1 , e2 = n - (i - mid + 1) - 1 ;
array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
h1[0] == h2[0] && h1[1] == h2[1] ? lo = mid : hi = mid ;
}
actual += lo ; int L = lo ;
A1[i+2]--, A1[i+L+1]++, A2[i+1]+=L-1;
B1[i-L+1]++, B1[i]--, B2[i]-=L-1;
if(i+L+1 < n && i-L-1 >= 0){
if( s[i+L+1] == s[i-L-1]){
lo = L + 2 , hi = min(i+1, n-i) + 1 ;
while(hi-lo>1){
int mid = (hi+lo)/2 ;
int s1 = i + L + 1, e1 = i + mid - 1 ;
int s2 = n - (i-L-1) - 1 , e2 = n - (i-mid+1) - 1 ;
array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
h1[0] == h2[0] && h1[1] == h2[1] ? lo = mid : hi = mid ;
}
inc[i+L][s[i-L]-'a'] += lo - L ;
inc[i-L][s[i+L]-'a'] += lo - L ;
}else{
inc[i+L][s[i-L]-'a'] += 1 ;
inc[i-L][s[i+L]-'a'] += 1 ;
}
}
}
// solve for even len
if(i>0 && s[i] == s[i-1]){
int lo = 1, hi = min(i, n-i) + 1 ;
while(hi-lo>1){
int mid = (hi+lo)/2 ;
int s1 = i, e1 = i + mid - 1 ;
int s2 = n - (i-1) - 1 , e2 = n - (i - mid) - 1 ;
array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
h1[0] == h2[0] && h1[1] == h2[1] ? lo = mid : hi = mid ;
}
actual += lo ; int L = lo ;
A1[i+1]--, A1[i+L+1]++, A2[i]+=L;
B1[i-L]++, B1[i]--, B2[i]-=L;
if(i+L+1 < n && i-L-1 >= 0){
if( s[i+L+1] == s[i-L-1]){
lo = L + 2 , hi = min(i+1, n-i) + 1 ;
while(hi-lo>1){
int mid = (hi+lo)/2 ;
int s1 = i + L + 1, e1 = i + mid - 1 ;
int s2 = n - (i-L-2) - 1 , e2 = n - (i - mid) - 1 ;
array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
h1[0] == h2[0] && h1[1] == h2[1] ? lo = mid : hi = mid ;
}
inc[i+L][s[i-L-1]-'a'] += lo - L ;
inc[i-L-1][s[i+L]-'a'] += lo - L ;
}else{
inc[i+L][s[i-L-1]-'a'] += 1 ;
inc[i-L-1][s[i+L]-'a'] += 1 ;
}
}
}else if(i>0){
int L = 0 ;
inc[i+L][s[i-L-1]-'a'] += 1 ;
inc[i-L-1][s[i+L]-'a'] += 1 ;
}
}
f(i,1,N) A1[i] += A1[i-1], B1[i] += B1[i-1];
f(i,0,N) A1[i] += A2[i], B1[i] += B2[i];
f(i,1,N) A1[i] += A1[i-1], B1[i] += B1[i-1];
int ans = actual ;
f(i,0,n){
f(j,0,26){
if( (int)(s[i]-'a') == j) continue ;
ans = max(ans, actual + inc[i][j] - A1[i] - B1[i]) ;
}
}
cout << ans ;
}
Compilation message
palinilap.cpp: In function 'void setIO(std::string)':
palinilap.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
31 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
32 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
