/**
* 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) {
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;
}
struct Fenwick_tree {
int n, BIT[nax];
void reseter(int _n) {
n = _n;
for (int i = 1; i <= n; ++i) {
BIT[i] = 0;
}
}
void update(int idx, int val) {
assert(idx);
for (int i = idx; i <= n; i += i & (-i)) {
(BIT[i] += val) %= mod;
}
}
int get(int r) {
int res = 0;
for (int i = r; i > 0; i -= i & (-i)) {
(res += BIT[i]) %= mod;
}
return res;
}
};
#define Fi first
#define Se second
vector<pair<int, int>> memo[nax][2][2];
Fenwick_tree hp, revhp;
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];
}
}
}
hp.reseter(n + 7);
revhp.reseter(n + 7);
for (int i = 1; i <= n; ++i) {
hp.update(i, t[i] * pw[i] % mod);
revhp.update(i, revt[i] * pw[i] % mod);
}
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;
hp.update(i, (j * pw[i] % mod - hp.get(i) + hp.get(i - 1) + mod) % mod);
revhp.update(n - i + 1, (j * pw[n - i + 1] % mod - revhp.get(n - i + 1) + revhp.get(n - i) + mod) % mod);
auto get_hashp = [&](int l, int r) {
return (hp.get(r) - hp.get(l - 1) + mod) * inv[l - 1] % mod;
};
auto get_revhashp = [&](int l, int r) {
return (revhp.get(r) - revhp.get(l - 1) + mod) * inv[l - 1] % mod;
};
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 = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 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 = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (auto [e, z] : memo[i - 1][0][1]) {
sum -= z;
int l = 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid + 1, e) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (auto [e, z] : memo[i + 1][0][0]) {
sum -= z;
int l = 1, r = min(e, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid + 1, e) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (auto [e, z] : memo[i - 1][1][1]) {
sum -= z;
int l = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l--;
sum += l;
}
for (auto [e, z] : memo[i + 1][1][0]) {
sum -= z;
int l = 1, r = min(e - 1, n - e + 1);
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hashp(e - mid, e - 1) == get_revhashp(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];
hp.update(i, (s[i] * pw[i] % mod - hp.get(i) + hp.get(i - 1) + mod) % mod);
revhp.update(n - i + 1, (s[i] * pw[n - i + 1] % mod - revhp.get(n - i + 1) + revhp.get(n - i) + mod) % mod);
}
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 <= 50) {
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
11184 KB |
Output is correct |
| 2 |
Correct |
26 ms |
11196 KB |
Output is correct |
| 3 |
Correct |
20 ms |
11308 KB |
Output is correct |
| 4 |
Correct |
18 ms |
11204 KB |
Output is correct |
| 5 |
Correct |
18 ms |
11272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
233 ms |
12260 KB |
Output is correct |
| 2 |
Correct |
255 ms |
12268 KB |
Output is correct |
| 3 |
Correct |
253 ms |
12208 KB |
Output is correct |
| 4 |
Correct |
115 ms |
11716 KB |
Output is correct |
| 5 |
Correct |
191 ms |
12008 KB |
Output is correct |
| 6 |
Correct |
241 ms |
12164 KB |
Output is correct |
| 7 |
Correct |
182 ms |
12084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
28576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
