#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
mt19937 gen(33);
uniform_int_distribution<> rd(1, 1000000000);
int pre[100005];
int prer[100005];
int pw[100005];
int p;
int all[100005][26];
int n;
int take(int l, int r) {
int res = pre[r];
if (l) {
res -= pw[r - l + 1] * pre[l - 1] % mod;
}
res += mod;
res %= mod;
return res;
}
int takerev(int l, int r) {
int res = prer[r];
if (r) {
res -= pw[r - l + 1] * prer[l - 1] % mod;
}
res += mod;
res %= mod;
return res;
}
bool eq(int a, int b, int c, int d) {
return take(a, b) == takerev(n - d - 1, n - c - 1);
}
signed main() {
p = rd(gen);
string s;
cin >> s;
n = s.length();
auto srev = s;
reverse(srev.begin(), srev.end());
pw[0] = 1;
for (int i = 1; i < n; ++i) pw[i] = pw[i - 1] * p % mod;
pre[0] = s[0] % mod;
for (int i = 1; i < n; ++i) {
pre[i] = (pre[i - 1] * p % mod + s[i]) % mod;
}
prer[0] = srev[0] % mod;
for (int i = 1; i < n; ++i) {
prer[i] = (prer[i - 1] * p % mod + srev[i]) % mod;
}
int act = 0;
vector<int> diff(n + 5);
// cout << pw[2] << endl;
// cout << take(0, 1) << ' ' << take(2, 3) << endl;
for (int i = 0; i < n; ++i) {
for (int j = i; j <= i + 1; ++j) {
if (j >= n) continue;
int lo = 0, hi = min(i, n - j - 1);
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (eq(i - mid, i, j, j + mid)) {
// if (take(i - mid, i) == take(j, j + mid)) {
lo = mid + 1;
} else hi = mid - 1;
}
if (hi >= 0) {
// assert(take(i - hi, i) == take(j, j + hi));
}
// cout << "hi" << hi << ' ' << take(0, 1) << ' ' << takerev(0, 1) << endl;
act += hi + 1;
if (i == j) {
diff[i - hi] += -1;
diff[i] -= -1;
diff[i] += hi;
diff[i + 1] += -2 * hi;
diff[i + 2] += hi;
diff[i + 1] += 1;
diff[i + hi + 1] -= 1;
} else {
diff[i - hi] += -1;
diff[i + 1] -= -1;
diff[i + 2] += 1;
diff[i + 1 + hi + 2] -= 1;
}
int x = i - hi - 1;
int y = j + hi + 1;
if (x < 0 or y > n - 1) continue;
lo = 1, hi = min(x, n - y - 1);
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (eq(x - mid, x - 1, y + 1, y + mid)) {
// if (take(x - mid, x - 1) == take(y + 1, y + mid)) {
lo = mid + 1;
} else hi = mid - 1;
}
if (hi > 0) {
// assert(take(x - hi, x - 1) == take(y + 1, y + hi));
}
// if (i == 0 and j == 1) cout << x << ' ' << y << ' ' << hi + 1 << endl;
all[x][s[y] - 'a'] += hi + 1;
all[y][s[x] - 'a'] += hi + 1;
}
}
int ans = act;
int cur = act;
// cout << cur << endl;
int delta = 0;
for (int i = 0; i < n; ++i) {
delta += diff[i];
cur += delta;
// cout << delta << endl;
for (int j = 0; j < 26; ++j) {
if ((s[i] - 'a') == j) continue;
// cout << all[i][j] << ' ';
// if (i == 1 and j == 2) cout << "INI " << all[i][j] << endl;
ans = max(ans, cur + all[i][j]);
// if (i == 1 and j == 0) cout << cur << endl;
// cout << i << ' ' << j << ' ' << cur + all[i][j] + 1 << endl;
}
// cout << endl;
// cout << cur << ' ';
}
// cout << endl;
cout << ans << endl;
delta += diff[n];
cur += delta;
assert(cur == act);
// cout << cur << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
1492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
24028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
