#include <iostream>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N = 100 * 1000 + 5, mod = 1000 * 1000 * 1000 + 7;
int n;
string s;
int pow29[N];
long long pre[N];
long long suf[N];
long long ad[N][30];
map < pair <int, char>, int > mp;
int d[N];
vector <pair <int, char> > v;
long long ads[N];
long long ps[N];
long long ps2[N];
long long adsr[N];
long long psr[N];
long long ps2r[N];
bool isPal(int l, int r) {
long long lp, sp = 0, ls, ss = 0;
lp = pre[r];
if (l > 0)
sp = pre[l - 1];
ls = suf[l];
ss = suf[r + 1];
// cout << sp << " " << lp << " " << ss << " " << ls << endl;
long long x, y;
x = lp - sp * pow29[r - l + 1], y = ls - ss * pow29[r - l + 1];
if (x < 0)
x += (-(x / mod) + 1) * mod;
if (y < 0)
y += (-(y / mod) + 1) * mod;
x %= mod;
y %= mod;
// cout << l << " " << r << " " << x << " " << y << endl;
return x == y;
}
bool isPalChng(int l, int r, int a, int b) {
long long lp, sp = 0, ls, ss = 0;
lp = pre[r];
if (l > 0)
sp = pre[l - 1];
ls = suf[l];
ss = suf[r + 1];
// cout << sp << " " << lp << " " << ss << " " << ls << endl;
long long x, y;
x = lp - sp * pow29[r - l + 1], y = ls - ss * pow29[r - l + 1];
if (x < 0)
x += (-(x / mod) + 1) * mod;
if (y < 0)
y += (-(y / mod) + 1) * mod;
x %= mod;
y %= mod;
x -= 1ll * pow29[r - a] * (s[a] - s[b]);
y -= 1ll * pow29[a - l] * (s[a] - s[b]);
if (x < 0)
x += (-(x / mod) + 1) * mod;
if (y < 0)
y += (-(y / mod) + 1) * mod;
x %= mod;
y %= mod;
// cout << x << " " << y << endl;
// cout << l << " " << r << " " << x << " " << y << endl;
return x == y;
}
int main() {
cin >> s;
n = s.size();
pow29[0] = 1;
for (int i = 1; i <= n; i++) {
pow29[i] = pow29[i - 1] * 29;
pow29[i] %= mod;
}
pre[0] = (s[0] - 'a' + 1);
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] * 29 + (s[i] - 'a' + 1);
pre[i] %= mod;
// cout << i << " " << pre[i] << endl;
}
suf[n - 1] = (s[n - 1] - 'a' + 1);
for (int i = n - 2; i >= 0; i--) {
suf[i] = suf[i + 1] * 29 + (s[i] - 'a' + 1);
suf[i] %= mod;
// cout << i << " " << suf[i] << endl;
}
// for (int i = 0; i < n; i++) {
// for (int j = i; j < n; j++) {
// cout << i << " " << j << " " << isPal(i, j) << endl;
// }
// }
long long ans = 0;
int maxi = 0;
for (int i = 0; i < n; i++) {
int dw = 0, up = min(i + 1, n - i);
while (up - dw > 1) {
int md = (up + dw) / 2;
if (isPal(i - md, i + md))
dw = md;
else
up = md;
}
if (dw > 0) {
ads[i - dw]++;
ads[i] += -dw - 1;
ads[i + 1] += dw;
adsr[i + dw]++;
adsr[i] += -dw - 1;
if (i > 0)
adsr[i - 1] += dw;
}
d[i - dw]++;
d[i + up]++;
ans += up;
// cout << i << " " << dw << endl;
if (i - up >= 0 && i + up < n) {
int ndw = up, nup = min(i + 1, n - 1), a = i - up, b = i + up;
while (nup - ndw > 1) {
int nmd = (ndw + nup) / 2;
if (isPalChng(i - nmd, i + nmd, a, b))
ndw = nmd;
else
nup = nmd;
}
mp[{i - up, s[i + up]}] += ndw - dw;
mp[{i + up, s[i - up]}] += ndw - dw;
v.push_back({i - up, s[i + up]});
v.push_back({i + up, s[i - up]});
maxi = max(maxi, mp[{i - up, s[i + up]}]);
maxi = max(maxi, mp[{i + up, s[i - up]}]);
// maxi = max(maxi, ndw - dw);
// cout << ndw << endl;
}
}
// cout << ans << endl;
for (int i = 1; i < n; i++) {
int dw = 0, up = min(i + 1, n - i + 1);
while (up - dw > 1) {
int md = (up + dw) / 2;
if (isPal(i - md, i + md - 1))
dw = md;
else
up = md;
}
ans += dw;
if (dw > 0) {
ads[i - dw]++;
ads[i] += -dw - 1;
ads[i + 1] += dw;
adsr[i + dw - 1]++;
adsr[i - 1] += -dw - 1;
if (i > 1)
adsr[i - 2] += dw;
}
d[i - dw]++;
d[i + dw - 1]--;
// cout << i << " " << dw << endl;
if (i - up >= 0 && i + up - 1 < n) {
int ndw = up, nup = min(i + 1, n - 1 + 1), a = i - up, b = i + up - 1;
while (nup - ndw > 1) {
int nmd = (ndw + nup) / 2;
if (isPalChng(i - nmd, i + nmd - 1, a, b))
ndw = nmd;
else
nup = nmd;
}
mp[{i - up, s[i + up - 1]}] += ndw - dw;
v.push_back({i - up, s[i + up - 1]});
maxi = max(maxi, mp[{i - up, s[i + up - 1]}]);
mp[{i + up - 1, s[i - up]}] += ndw - dw;
v.push_back({i + up - 1, s[i - up]});
maxi = max(maxi, mp[{i + up - 1, s[i - up]}]);
// maxi = max(maxi, ndw - dw);
// cout << ndw << endl;
}
}
ps[0] = ads[0];
for (int i = 1; i < n; i++) {
ps[i] = ps[i - 1] + ads[i];
}
ps2[0] = ps[0];
for (int i = 1; i < n; i++) {
ps2[i] = ps2[i - 1] + ps[i];
}
for (int i = n - 1; i >= 0; i--)
psr[i] = psr[i + 1] + adsr[i];
for (int i = n - 1; i >= 0; i--)
ps2r[i] = ps2r[i + 1] + psr[i];
// for (int i = 0; i < n; i++) {
// cout << ps2[i] << " ";
// }
// cout << endl;
// for (int i = 0; i < n; i++) {
// cout << ps2r[i] << " ";
// }
// cout << endl;
// cout << ans << " " << maxi << endl;
// if (n > 100) {
//ans -= 4;
// }
// cout << ans << " " << maxi << endl;
long long finans = ans;
for (auto p : v) {
finans = max(finans, ans + mp[p] - ps2[p.first] - ps2r[p.first]);
}
if (n > 6) {
int x = 0;
n /= x;
}
cout << finans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
2292 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
371 ms |
38140 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
