#include <iostream>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N = 100 * 1000 + 5, mod = 1000 * 1000 * 1000 + 21;
int n;
string s;
long long pow29[N];
long long pre[N];
long long suf[N];
long long ad[N][32];
map < pair <int, char>, long long > mp;
long long 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;
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:99:6: warning: unused variable 'maxi' [-Wunused-variable]
int maxi = 0;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1396 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1196 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1404 KB |
Output is correct |
| 6 |
Correct |
13 ms |
1524 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
318 ms |
17640 KB |
Output is correct |
| 2 |
Correct |
341 ms |
17884 KB |
Output is correct |
| 3 |
Correct |
184 ms |
16360 KB |
Output is correct |
| 4 |
Correct |
341 ms |
23020 KB |
Output is correct |
| 5 |
Correct |
345 ms |
23276 KB |
Output is correct |
| 6 |
Correct |
340 ms |
23156 KB |
Output is correct |
| 7 |
Correct |
342 ms |
23180 KB |
Output is correct |
| 8 |
Correct |
96 ms |
8452 KB |
Output is correct |
| 9 |
Correct |
358 ms |
23132 KB |
Output is correct |
| 10 |
Correct |
333 ms |
23000 KB |
Output is correct |
| 11 |
Correct |
339 ms |
17844 KB |
Output is correct |
| 12 |
Correct |
308 ms |
17816 KB |
Output is correct |
| 13 |
Correct |
351 ms |
18592 KB |
Output is correct |
| 14 |
Correct |
339 ms |
24680 KB |
Output is correct |
| 15 |
Correct |
334 ms |
23428 KB |
Output is correct |
| 16 |
Correct |
379 ms |
24080 KB |
Output is correct |
| 17 |
Correct |
446 ms |
35024 KB |
Output is correct |
| 18 |
Correct |
385 ms |
17756 KB |
Output is correct |
| 19 |
Correct |
423 ms |
35088 KB |
Output is correct |
