/**
* author: longvu
* created: 10/26/22 10:01:42
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(100091);
const int mod = 1234567891;
template<class X, class Y>
bool maximize(X& x, const Y y) {
if (y > x) {x = y; return true;}
return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
if (y < x) {x = y; return true;}
return false;
}
bool ok(string s) {
string revs = s;
reverse(all(revs));
return (s == revs);
}
int n;
string s;
int sub1() {
int res = 0;
for (int i = 1; i <= n; ++i) {
string t = s;
for (char j = 'a'; j <= 'z'; ++j) {
t[i] = j;
int sum = 0;
for (int e = 1; e <= n; ++e) {
for (int f = 1; f <= e; ++f) {
if (ok(t.substr(f, e - f + 1))) {
sum++;
}
}
}
maximize(res, sum);
}
}
return res;
}
int expo(int a, int b) {
if (!b) {
return 1;
}
int tmp = expo(a, b / 2);
if (b & 1) {
return tmp * tmp % mod * (a % mod) % mod;
}
return tmp * tmp % mod;
}
const int BASE = (int)(311);
int pw[nax], inv[nax];;
void precal() {
pw[0] = 1;
for (int i = 1; i < nax; ++i) {
pw[i] = BASE * pw[i - 1] % mod;
}
inv[nax - 1] = expo(pw[nax - 1], mod - 2);
for (int i = nax - 2; i >= 0; --i) {
inv[i] = BASE * inv[i + 1] % mod;
}
}
int get_hash(int h[], int l, int r) {
assert(l <= r);
return (h[r] - h[l - 1] + mod) * inv[l - 1] % mod;
}
int h[nax], hrev[nax];
int sub2() {
precal();
int res = 0;
string t = s, revt = s.substr(1);
reverse(all(revt));
revt = '$' + revt;
for (int i = 1; i <= n; ++i) {
for (char j = 'a'; j <= 'z'; ++j) {
t[i] = revt[n - i + 1] = j;
for (int e = 1; e <= n; ++e) {
h[e] = (t[e] * pw[e] % mod + h[e - 1]) % mod;
}
for (int e = 1; e <= n; ++e) {
hrev[e] = (revt[e] * pw[e] % mod + hrev[e - 1]) % mod;
}
int sum = 0;
for (int e = 1; e <= n; ++e) {
int l = 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid + 1, e) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (int e = 2; e <= n; ++e) {
if (t[e] == t[e - 1]) {
int l = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 1) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
}
maximize(res, sum);
}
t[i] = revt[n - i + 1] = s[i];
}
return res;
}
#define Fi first
#define Se second
vector<pair<int, int>> memo[nax][2][2];
int pre[nax][3][2], mp[nax];
int sub3() {
precal();
int res = 0;
string t = s, revt = s.substr(1);
reverse(all(revt));
revt = '$' + revt;
for (int e = 1; e <= n; ++e) {
h[e] = (t[e] * pw[e] % mod + h[e - 1]) % mod;
}
for (int e = 1; e <= n; ++e) {
hrev[e] = (revt[e] * pw[e] % mod + hrev[e - 1]) % mod;
}
int res_base = 0;
for (int e = 1; e <= n; ++e) {
int l = 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid + 1, e) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
if (l > 1) {
pre[e - l + 1][0][0]++;
pre[e][0][0]--;
pre[e - l + 1][1][0] += e;
pre[e][1][0] -= e;
pre[e - l + 1][2][0] += l;
pre[e][2][0] -= l;
pre[e + 1][0][1]++;
pre[e + l][0][1]--;
pre[e + 1][1][1] += e;
pre[e + l][1][1] -= e;
pre[e + 1][2][1] += l;
pre[e + l][2][1] -= l;
}
memo[e - l + 1][0][0].push_back({e, l});
memo[e + l - 1][0][1].push_back({e, l});
res_base += l;
}
for (int e = 2; e <= n; ++e) {
if (t[e] == t[e - 1]) {
int l = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 1) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
pre[e - l][0][0]++;
pre[e][0][0]--;
pre[e - l][1][0] += e - 1;
pre[e][1][0] -= e - 1;
pre[e - l][2][0] += l;
pre[e][2][0] -= l;
pre[e + 1][0][1]++;
pre[e + l][0][1]--;
pre[e + 1][1][1] += e;
pre[e + l][1][1] -= e;
pre[e + 1][2][1] += l;
pre[e + l][2][1] -= l;
mp[e] = l;
memo[e - l][1][0].push_back({e, l});
memo[e + l - 1][1][1].push_back({e, l});
res_base += l;
}
}
maximize(res, res_base);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= 2; ++j) {
for (int e = 0; e <= 1; ++e) {
pre[i][j][e] += pre[i - 1][j][e];
}
}
}
for (int i = 1; i <= n; ++i) {
for (char j = 'a'; j <= 'z'; ++j) {
if (j != s[i]) {
t[i] = revt[n - i + 1] = j;
int sum = res_base;
sum -= pre[i][2][0];
sum += pre[i][1][0] - i * pre[i][0][0];
sum -= pre[i][2][1];
sum += i * pre[i][0][1] - pre[i][1][1];
if (s[i] == s[i + 1]) {
sum -= mp[i + 1];
}
if (t[i] == t[i + 1]) {
int e = i + 1, l = 2, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 2) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + 1) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
if (s[i - 1] == s[i]) {
sum -= mp[i];
}
if (t[i - 1] == t[i]) {
int e = i, l = 2, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 2) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + 1) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (auto [e, z] : memo[i - 1][0][1]) {
if (t[i] == t[e - z]) {
sum -= z;
int x = z + 1, l = x + 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid + 1, e - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
}
for (auto [e, z] : memo[i + 1][0][0]) {
if (t[i] == t[e + z]) {
sum -= z;
int x = z + 1, l = x + 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid + 1, e - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
}
for (auto [e, z] : memo[i - 1][1][1]) {
if (t[i] == t[e - 1 - z]) {
sum -= z;
int x = z + 1, l = x + 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 1 - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
}
for (auto [e, z] : memo[i + 1][1][0]) {
if (t[i] == t[e + z]) {
sum -= z;
int x = z + 1, l = x + 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(h, e - mid, e - 1 - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
}
maximize(res, sum);
}
}
t[i] = revt[n - i + 1] = s[i];
}
return res;
}
const int sub = 1;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> s;
n = sz(s);
s = '$' + s;
// if (n <= 100) {
// if (!sub) cout << "Sub1: " << '\n';
// cout << sub1() << '\n';
// if (sub) return 0;
// }
// if (n <= 500) {
// if (!sub) cout << "Sub2: " << '\n';
// cout << sub2() << '\n';
// if (sub) return 0;
// }
if (!sub) cout << "Sub3: " << '\n';
cout << sub3() << '\n';
if (sub) return 0;
return 0;
}
Compilation message
palinilap.cpp: In function 'long long int sub3()':
palinilap.cpp:262:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
262 | for (auto [e, z] : memo[i - 1][0][1]) {
| ^
palinilap.cpp:278:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
278 | for (auto [e, z] : memo[i + 1][0][0]) {
| ^
palinilap.cpp:294:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
294 | for (auto [e, z] : memo[i - 1][1][1]) {
| ^
palinilap.cpp:310:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
310 | for (auto [e, z] : memo[i + 1][1][0]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11220 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11296 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11220 KB |
Output is correct |
| 4 |
Correct |
10 ms |
11220 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12200 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12112 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12048 KB |
Output is correct |
| 4 |
Correct |
10 ms |
11720 KB |
Output is correct |
| 5 |
Correct |
13 ms |
11956 KB |
Output is correct |
| 6 |
Correct |
13 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
12 ms |
12016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
27208 KB |
Output is correct |
| 2 |
Correct |
108 ms |
28044 KB |
Output is correct |
| 3 |
Correct |
115 ms |
28136 KB |
Output is correct |
| 4 |
Correct |
135 ms |
26352 KB |
Output is correct |
| 5 |
Correct |
152 ms |
26420 KB |
Output is correct |
| 6 |
Correct |
147 ms |
26200 KB |
Output is correct |
| 7 |
Correct |
147 ms |
26380 KB |
Output is correct |
| 8 |
Correct |
92 ms |
28216 KB |
Output is correct |
| 9 |
Correct |
152 ms |
26356 KB |
Output is correct |
| 10 |
Correct |
138 ms |
26356 KB |
Output is correct |
| 11 |
Correct |
126 ms |
28144 KB |
Output is correct |
| 12 |
Correct |
147 ms |
30312 KB |
Output is correct |
| 13 |
Correct |
138 ms |
26900 KB |
Output is correct |
| 14 |
Correct |
141 ms |
26440 KB |
Output is correct |
| 15 |
Correct |
142 ms |
26740 KB |
Output is correct |
| 16 |
Correct |
130 ms |
28100 KB |
Output is correct |
| 17 |
Correct |
123 ms |
25100 KB |
Output is correct |
| 18 |
Correct |
145 ms |
26328 KB |
Output is correct |
| 19 |
Correct |
129 ms |
25096 KB |
Output is correct |
