#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int MOD = 420691273;
ll add[N][26];
ll prv[N];
ll pw[N];
ll pw2[N];
ll p[N];
ll pref[N];
ll suff[N];
ll diff[N];
ll diff2[N];
int n;
string s;
ll get_pref(int l, int r){
if(l == 0)return pref[r];
return ((pref[r] - pref[l - 1]) % MOD + MOD) % MOD;
}
ll get_suff(int l, int r){
return ((suff[l] - suff[r + 1]) % MOD + MOD) % MOD;
}
int find_range(int &lf, int &rg, bool b){
if(min(lf, n - 1 - rg) < 0)return 0;
if(s[lf] != s[rg])return 0;
int l = 0, r = min(lf, n - 1 - rg);
// cout << l << ' ' << r << endl;
// cout << lf << ' ' << rg << '\n';
while(l < r){
int m = (l + r + 1)/2;
if(get_pref(lf - m, rg + m) * pw[(n - 1) - (rg + m)] % MOD == get_suff(lf - m, rg + m) * pw[lf - m] % MOD)l = m;
else r = m - 1;
}
//cout << l << endl;
++l;
lf -= l; rg += l;
return l;
}
int get_range(int lf, int rg){
if(min(lf, n - 1 - rg) < 0)return 0;
int l = 0, r = min(lf, n - 1 - rg);
if(r == 0)return 1;
++l;
if(s[lf - l] != s[rg + l])return l;
lf -= l;
rg += l;
int cur_l = l;
l = 0;
--r;
// cout << l << ' ' << r << endl;
// cout << lf << ' ' << rg << '\n';
while(l < r){
int m = (l + r + 1)/2;
if(get_pref(lf - m, lf) * pw[(n - 1) - (rg + m)] % MOD == get_suff(rg, rg + m) * pw[lf - m] % MOD)l = m;
else r = m - 1;
}
//cout << l << endl;
++l;
lf -= l; rg += l;
return l + cur_l;
}
// consider checking palindrome with hashing and binary search
// adding 1,2,3,4,5 arithmetic sequence with pending/segtree
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> s;
n = s.length();
pw[0] = 1;
for(int i = 1; i < n; ++i)pw[i] = pw[i - 1] * 37 % MOD;
for(int i = 0; i < n; ++i){
pref[i] = pw[i] * (s[i] - 'a' + 1) % MOD;
if(i > 0)pref[i] += pref[i - 1];
pref[i] %= MOD;
}
for(int i = n - 1; i >= 0; --i){
suff[i] = pw[n - 1 - i] * (s[i] - 'a' + 1) % MOD;
if(i < n - 1)suff[i] += suff[i + 1];
suff[i] %= MOD;
}
ll cnt = 0;
for(int i = 0; i < n; ++i){
int l = i, r = i;
int cur_cnt = find_range(l, r, 0);
// while(l >= 0 && r < n && s[l] == s[r]){
// ++cur_cnt;
// --l; ++r;
// }
cnt += cur_cnt;
cur_cnt = i - l - 1;
diff[l + 1]++;
diff[i]--;
if(l + 1 < i){
diff2[l + 2]++;
diff2[i]--;
diff[i] -= cur_cnt - 1;
}
diff[i + 1] += cur_cnt;
diff[r] -= cur_cnt;
if(i + 1 < r){
diff2[i + 2]--;
diff2[r + 1]++;
diff[r] += cur_cnt;
}
// int cur_l = l, cur_r = r;
// cur_cnt = 0;
// while(cur_l + 2 < cur_r){
// ++cur_l; --cur_r;
// ++cur_cnt;
// prv[cur_l] += cur_cnt;
// prv[cur_r] += cur_cnt;
// }
int lf = l, rg = r;
int cnt_add = get_range(l, r);
//cout << l << ' ' << r << ' ' << cnt_add << endl;
// while(l >= 0 && r < n){
// --l; ++r;
// ++cnt_add;
// if(s[l] != s[r])break;
// }
//cout << i << " -> " << cnt_add << ' ' << lf << ' ' << rg << endl;
if(cnt_add && lf >= 0 && rg < n){
add[lf][s[rg] - 'a'] += cnt_add;
add[rg][s[lf] - 'a'] += cnt_add;
}
}
for(int i = 1; i < n; ++i){
int l = i - 1, r = i;
int cur_cnt = find_range(l, r, 0);
// while(l >= 0 && r < n && s[l] == s[r]){
// ++cur_cnt;
// --l; ++r;
// }
cnt += cur_cnt;
cur_cnt = i - 1 - l;
if(l + 1 < r){
diff[l + 1]++;
diff[i]--;
if(l + 1 < i - 1){
diff2[l + 2]++;
diff2[i]--;
diff[i] -= cur_cnt - 1;
}
diff[i] += cur_cnt;
diff[r] -= cur_cnt;
if(i < r - 1){
diff2[i + 1]--;
diff2[r]++;
diff[r - 1] += cur_cnt;
}
}
// int cur_l = l, cur_r = r;
// cur_cnt = 0;
// while(cur_l + 2 < cur_r){
// ++cur_l; --cur_r;
// ++cur_cnt;
// prv[cur_l] += cur_cnt;
// prv[cur_r] += cur_cnt;
// }
int lf = l, rg = r;
int cnt_add = get_range(l, r);
// while(l >= 0 && r < n){
// --l; ++r;
// ++cnt_add;
// if(s[l] != s[r])break;
// }
if(cnt_add && lf >= 0 && rg < n){
add[lf][s[rg] - 'a'] += cnt_add;
add[rg][s[lf] - 'a'] += cnt_add;
}
}
// for(int i = 0; i <= n; ++i)cout << diff[i] << ' ';
// cout << '\n';
// for(int i = 0; i <= n; ++i)cout << diff2[i] << ' ';
// cout << '\n';
for(int i = 0; i < n; ++i){
if(i > 0)diff2[i] += diff2[i - 1];
diff[i] += diff2[i];
if(i > 0)diff[i] += diff[i - 1];
prv[i] += diff[i];
}
//for(int i = 0; i <= n; ++i)cout << prv[i] << ' ';
//cout << '\n';
ll max_add = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < 26; ++j){
max_add = max(max_add, add[i][j] - prv[i]);
}
}
//cout << add[5][1] << endl;
//cout << cnt << '\n';
cout << cnt + max_add << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
25660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
