#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 pw[100005];
int p;
int all[100005][26];
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;
}
signed main() {
p = rd(gen);
string s;
cin >> s;
int n = s.length();
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 = 0; i < n; ++i) {
pre[i] = (pre[i - 1] * p % mod + s[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 (take(i - mid, i) == take(j, j + mid)) {
lo = mid + 1;
} else hi = mid - 1;
}
// cout << hi << endl;
act += hi + 1;
if (i == j) {
diff[i - hi] += -1;
diff[i + 1] -= -1;
diff[i + 1] += 1;
diff[i + hi + 2] -= 1;
} else if (s[i] == s[j]) {
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 (take(x - mid, x - 1) == take(y + 1, y + mid)) {
lo = mid + 1;
} else hi = mid - 1;
}
all[x][s[y] - 'a'] += hi + 1;
all[y][s[x] - 'a'] += hi + 1;
}
// {
// int lo = 0, hi = min(i, n - i - 1);
// while (lo <= hi) {
// int mid = (lo + hi) / 2;
// if (take(i - mid, i - 1) == take(i + 1, i + mid)) {
// lo = mid + 1;
// } else hi = mid - 1;
// }
// cout << hi << endl;
// diff[i - hi] += -1;
// diff[i + 1] -= -1;
// diff[i + 1] += 1;
// diff[max(i + 2, i + hi + 2)] -= 1;
// act += hi + 1;
// if (i - hi - 1 >= 0 and i + hi + 1 < n) {
// all[i - hi - 1][s[i + hi + 1] - 'a']++;
// all[i + hi + 1][s[i - hi - 1] - 'a']++;
// }
// }
// if (i == n - 1) break;
// if (s[i] != s[i + 1]) continue;
// // continue;
// {
// int lo = 0, hi = min(i, n - i - 2);
// while (lo <= hi) {
// int mid = (lo + hi) / 2;
// if (take(i - lo, i) == (take(i + 1, i + 1 + lo))) {
// lo = mid + 1;
// } else hi = mid - 1;
// }
// // cout << hi << endl;
// diff[i - hi] += -1;
// diff[i + 1] -= -1;
// diff[i + 2] += 1;
// diff[i + 1 + hi + 2] -= 1;
// act += hi + 1;
// if (i - hi - 1 >= 0 and i + 1 + hi + 1 < n) {
// all[i - hi - 1][s[i + hi + 2] - 'a']++;
// all[i + hi + 2][s[i - hi - 1] - 'a']++;
// }
// }
}
int ans = act;
int cur = act;
// cout << cur << endl;
int delta = 0;
for (int i = 0; i < n; ++i) {
delta += diff[i];
cur += delta;
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] + 1);
}
// 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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1476 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
23204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
