#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 40;
const ll MOD = 1e9 + 7;
const ll INF = 3e18;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;
int n;
ll pw[N], h[N], rh[N];
ll f[N][26], bad[N];
ll get(int i, int j) {
return (h[j] - h[i - 1] * pw[j - i + 1] + MOD * MOD) % MOD;
}
ll getr(int i, int j) {
return (rh[i] - rh[j + 1] * pw[j - i + 1] + MOD * MOD) % MOD;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
string s; cin >> s;
n = s.size();
s = " " + s;
pw[0] = 1;
for (int i = 1; i <= n; i ++) {
pw[i] = (pw[i - 1] * base) % MOD;
h[i] = (h[i - 1] * base + s[i]) % MOD;
}
for (int i = n; i > 0; i --)
rh[i] = (rh[i + 1] * base + s[i]) % MOD;
ll sum = 0;
for (int i = 1; i <= n; i ++) {
int l = 0, r = min(i - 1, n - i);
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (get(i - mid, i) == getr(i, i + mid))
l = mid;
else r = mid - 1;
}
sum += l + 1;
for (int c = 0; c < 26; c ++) f[i][c] += l + 1;
bad[i] += l, bad[i + 1] -= l;
bad[i - l] ++, bad[i + l + 1] --;
if (1 < i - l && i + l < n) {
f[i - l - 1][s[i + l + 1] - 'a'] ++;
f[i + l + 1][s[i - l - 1] - 'a'] ++;
}
int x = l, L = i - l - 2, R = i + l + 2;
if (L < 1 || R > n) continue;
l = 0, r = min(L - 1, n - R);
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (get(L - mid, L) == getr(R, R + mid))
l = mid;
else r = mid - 1;
}
if (get(L - l, L) == getr(R, R + l)) {
f[i - x - 1][s[i + x + 1] - 'a'] += l + 1;
f[i + x + 1][s[i - x - 1] - 'a'] += l + 1;
}
}
for (int i = 1; i < n; i ++) {
int l = 0, r = min(i - 1, n - i);
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (get(i - mid, i) == getr(i + 1, i + 1 + mid))
l = mid;
else r = mid - 1;
}
if (get(i - l, i) == getr(i + 1, i + 1 + l)) {
sum += l + 1;
bad[i] += l, bad[i + 2] -= l;
bad[i - l] ++, bad[i + l + 2] --;
}
else l --;
if (1 < i - l && i + l + 1 < n) {
f[i - l - 1][s[i + l + 2] - 'a'] ++;
f[i + l + 2][s[i - l - 1] - 'a'] ++;
}
int x = l, L = i - l - 2, R = i + l + 3;
if (L < 1 || R > n) continue;
l = 0, r = min(L - 1, n - R);
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (get(L - mid, L) == getr(R, R + mid))
l = mid;
else r = mid - 1;
}
if (get(L - l, L) == getr(R, R + l)) {
f[i - x - 1][s[i + x + 2] - 'a'] += l + 1;
f[i + x + 2][s[i - x - 1] - 'a'] += l + 1;
}
}
ll ans = sum, cur = 0;
for (int i = 1; i <= n; i ++) {
cur += bad[i];
for (int c = 0; c < 26; c ++)
ans = max(ans, sum + f[i][c] - cur);
}
cout << ans;
}
/*
/\_/\ zzZ
(= -_-)
/ >u >u
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
24136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
