#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, unsigned long long>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define debug cerr << "OK\n";
const int N = (int)1e5 + 5;
const ll mod = (int)1e9 + 9;
const ll mod1 = (int)1e9 + 9;
const ll inf = (int)1e9;
const ll INF = (ll)1e18;
const ll P = 31;
int n;
pll p[N], h[N], q[N];
pll mi(pll a) {
return {(((-a.F) % mod) + mod) % mod, -a.S};
}
pll add(pll a, pll b) {
return {(((a.F + b.F) % mod) + mod) % mod, a.S + b.S};
}
pll mul(pll a, pll b) {
return {(a.F * b.F) % mod, a.S * b.S};
}
pll H(int l, int r) {
return add(h[r], mi(mul(h[l - 1], p[r - l + 1])));
}
pll Q(int l, int r) {
return add(q[r], mi(mul(q[l - 1], p[r - l + 1])));
}
bool ipal(int l1, int r1, int l2, int r2) {
auto [L, R] = mp(n - r2 + 1, n - l2 + 1);
return H(l1, r1) == Q(L, R);
}
ll us[N], uc[N], cs[N], sc[N], ch[N][27];
void solve() {
string s;
cin >> s;
n = sz(s);
string t = s;
reverse(all(t));
s = '#' + s;
t = '#' + t;
p[0] = {1, 1};
for (int i = 1; i <= n; i++) {
h[i].F = (h[i - 1].F * P + s[i] - 'a' + 1) % mod;
h[i].S = (h[i - 1].S * P + s[i] - 'a' + 1);
q[i].F = (q[i - 1].F * P + t[i] - 'a' + 1) % mod;
q[i].S = (q[i - 1].S * P + t[i] - 'a' + 1);
p[i].F = (p[i - 1].F * P) % mod;
p[i].S = (p[i - 1].S * P);
}
int pal = 0;
for (int i = 1; i <= n; i++) {
ll l = 1, r = min(i, n - i + 1), mx = 1;
while (l <= r) {
int mid = (l + r) / 2;
if (ipal(i - mid + 1, i + mid - 1, i - mid + 1, i + mid - 1)) {
l = mid + 1;
mx = mid;
} else r = mid - 1;
}
pal += mx;
if (mx > 1) {
sc[i - mx + 1]++;
sc[i]--;
us[i] -= (mx * (mx - 1)) / 2;
cs[i + 1]++;
cs[i + mx]--;
uc[i] -= (mx * (mx - 1)) / 2;
}
if (i - mx > 0 && i + mx <= n) {
int m = mx;
auto [L, R] = mp(i - mx, i + mx);
l = 2, r = min(L, n - R + 1);
mx = 1;
while (l <= r) {
int mid = (l + r) / 2;
if (ipal(L - mid + 1, L - 1, R + 1, R + mid - 1)) {
l = mid + 1;
mx = mid;
} else r = mid - 1;
}
ch[L][s[R] - 'a' + 1] += mx;
ch[R][s[L] - 'a' + 1] += mx;
}
l = 1, r = min(i, n - i), mx = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ipal(i - mid + 1, i + mid, i - mid + 1, i + mid)) {
l = mid + 1;
mx = mid;
} else r = mid - 1;
}
if (mx > 0) {
pal += mx;
sc[i - mx + 1]++;
sc[i + 1]--;
us[i + 1] -= ((mx + 1) * mx) / 2;
cs[i + 1]++;
cs[i + mx + 1]--;
uc[i] -= ((mx + 1) * mx) / 2;
}
if (i - mx > 0 && i + mx + 1 <= n) {
auto [L, R] = mp(i - mx, i + mx + 1);
l = 2, r = min(L, n - R + 1);
mx = 1;
while(l <= r) {
int mid = (l + r) / 2;
if (ipal(L - mid + 1, L - 1, R + 1, R + mid - 1)) {
l = mid + 1;
mx = mid;
} else r = mid - 1;
}
ch[L][s[R] - 'a' + 1] += mx;
ch[R][s[L] - 'a' + 1] += mx;
}
}
sc[n + 1] = sc[0] = cs[n + 1] = cs[0] = 0;
for (int i = 1; i <= n; i++) {
sc[i] += sc[i - 1];
cs[i] += cs[i - 1];
}
for (int i = 1; i <= n; i++) {
sc[i] += sc[i - 1] + us[i];
}
for (int i = n; i > 0; --i) {
cs[i] += cs[i + 1] + uc[i];
}
ll ans = pal;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 26; j++) {
if (j == s[i] - 'a' + 1) continue;
ans = max(ans, pal - sc[i] - cs[i] + ch[i][j]);
}
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int T = 1;
//cin >> T;
while (T--) solve();
return 0;
}
Compilation message
palinilap.cpp: In function 'void solve()':
palinilap.cpp:91:17: warning: unused variable 'm' [-Wunused-variable]
91 | int m = mx;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
29688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
