#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
using namespace std;
using ll = long long;
ll M = 1e9 + 7, P = 31;
string s;
int n;
int power[100000][26]={}; // how many new palindromes can be made if index i is changed to char c in power[i][c]
ll rsum[100000]={}, lsum[100000]={}, rsump[100000]={}, lsump[100000]={};
ll P2[100000];
ll hpref[100000], hsuff[100000];
ll get_hash(int a, int b) {
if (a == 0) return hpref[b];
return ((hpref[b] - P2[b-a+1]*hpref[a-1])%M + M) % M;
}
ll rev_hash(int a, int b) {
if (b == n-1) return hsuff[a];
return ((hsuff[a] - P2[b-a+1]*hsuff[b+1])%M + M) % M;
}
ll add(int ctr, bool even) { //cout << "eval: " << ctr << " " << even << endl;
ll res = 0;
int lc = ctr, rc = ctr + even;
int lo = 0, hi = min(lc+1, n-rc);
while (lo < hi) {
int mid = (lo+hi+1)/2;
if (get_hash(rc, rc+mid-1) == rev_hash(lc-mid+1, lc)) lo = mid;
else hi = mid-1;
}
res += lo;
if (lc+1 < n) {
rsum[lc+1] += lo + (even ? 0 : -1), rsump[lc+1]++;
if (rc+lo < n) rsump[rc+lo]--;
}
if (rc-1 >= 0) {
lsum[rc-1] += lo + (even ? 0 : -1), lsump[rc-1]++;
if (lc-lo >= 0) lsump[lc-lo]--;
}
ll val = lo;
// cout << "value: " << val << endl;
// update powers
if (lc-val < 0 || rc+val >= n) return res;
// update right end
ll dc = s[lc-val]-s[rc+val];
lo = val+1, hi = min(lc+1, n-rc);
while (lo < hi) {
int mid = (lo+hi+1)/2;
ll rh = (get_hash(rc, rc+mid-1) + dc*P2[mid-1-val] + (M<<5LL)) % M;
ll lh = rev_hash(lc-mid+1, lc);
if (rh == lh) lo = mid;
else hi = mid-1;
}
power[rc+val][s[lc-val]-'a'] += lo-val;
// cout << "rval: " << power[rc+val][s[lc-val]-'a'] << endl;
// update left end
dc = s[rc+val]-s[lc-val];
lo = val+1, hi = min(lc+1, n-rc);
while (lo < hi) {
int mid = (lo+hi+1)/2;
ll rh = get_hash(rc, rc+mid-1);
ll lh = (rev_hash(lc-mid+1, lc) + dc*P2[mid-1-val] + (M<<5LL)) % M;
//cout << "left bs: " << mid << " " << rh << " " << lh << endl;
if (rh == lh) lo = mid;
else hi = mid-1;
}
//cout << "updated left end: " << dc << " " << lo << endl;
power[lc-val][s[rc+val]-'a'] += lo-val;
// cout << "lval: " << power[lc-val][s[rc+val]-'a'] << endl;
return res;
}
int main() {
cin >> s;
n = s.size();
P2[0] = 1;
for (int i = 1; i < n; i++) P2[i] = P2[i-1] * P % M;
hpref[0] = s[0]-'a', hsuff[n-1] = s[n-1]-'a';
for (int i = 1; i < n; i++) hpref[i] = (hpref[i-1]*P + ll(s[i]-'a')) % M;
for (int i = n-1; i >= 0; i--) hsuff[i] = (hsuff[i+1]*P + ll(s[i]-'a')) % M;
// cout << "Debugging forward and reverse hashes: " << endl;
// cout << get_hash(3, 4) << " " << rev_hash(3, 4) << endl;
ll ans = 0;
// odd palindromes
for (int i = 0; i < n; i++) {
ans += add(i, 0);
ans += add(i, 1);
}
// cout << "pre ans: " << ans << endl;
// for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
// for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;
// for (int i = 0; i < n; i++) cout << lsump[i] << " "; cout << endl;
// for (int i = 0; i < n; i++) cout << rsump[i] << " "; cout << endl;
ll ds = 0, cnt = 0;
// carry out psums
for (int i = 0; i < n; i++) {
ds -= cnt;
ds += rsum[i], cnt += rsump[i];
rsum[i] = ds;
}
ds = 0, cnt = 0;
for (int i = n-1; i >= 0; i--) {
ds -= cnt;
ds += lsum[i], cnt += lsump[i];
lsum[i] = ds;
}
// cout << "Debugging new lsum, rsum, lsump, rsump: " << endl;
// for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
// for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;
ll dans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
dans = max(dans, power[i][j] - lsum[i] - rsum[i]);
}
}
cout << ans+dans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1076 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
9 ms |
980 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
11 ms |
1080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
16340 KB |
Output is correct |
| 2 |
Incorrect |
149 ms |
16212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
