#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9 + 7, mxn = 1e5 + 10;
ll n, a[mxn];
struct SegmentTree {
vector<ll> sum;
vector<pair<ll, ll>> lz;
SegmentTree(int n) {
sum.resize(4 * n);
lz.resize(4 * n);
}
void push(int k, int l, int r) {
if (lz[k].second) {
ll sz = (r - l + 1);
sum[k] += lz[k].first * sz;
sum[k] += lz[k].second * (sz * (sz + 1) / 2);
if (l != r) {
lz[k * 2].first += lz[k].first;
lz[k * 2].second += lz[k].second;
ll mid = (l + r) / 2;
lz[k * 2 + 1].first += lz[k].first + lz[k].second * (mid - l + 1);
lz[k * 2 + 1].second += lz[k].second;
}
lz[k] = {0, 0};
}
}
void update(int k, int l, int r, int i, int j) {
if (l > j || r < i) return;
if (i <= l && r <= j) {
lz[k].first += l - i;
lz[k].second += 1;
push(k, l, r);
return;
}
int mid = (l + r) / 2;
update(k * 2, l, mid, i, j);
update(k * 2 + 1, mid + 1, r, i, j);
}
void get(int k, int l, int r, bool d) {
push(k, l, r);
if (l == r) {
if (d) a[l] += sum[k];
else a[n - l - 1] += sum[k];
return;
}
int mid = (l + r) / 2;
get(k * 2, l, mid, d);
get(k * 2 + 1, mid + 1, r, d);
}
} sgtF(mxn), sgtB(mxn);
ll expo(ll a, ll b, ll mod) {
a %= mod;
ll res = 1;
while (b) {
if (b % 2 == 1) res = (res * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return res;
}
ll fact[mxn + 1], inv[mxn + 1], inv29 = expo(29, MOD - 2, MOD);
void precalc() {
inv[0] = expo(1, MOD - 2, MOD);
for (int i = 1; i <= mxn; i++) inv[i] = (inv[i - 1] * inv29) % MOD;
}
string s;
ll prf[mxn], suf[mxn], F[mxn], change[mxn][26];
ll getPRF(int l, int r) {
ll num = prf[r] - (l ? prf[l - 1] : 0);
num = (num + MOD) % MOD;
num = (num * inv[l]) % MOD;
return num;
}
ll getSUF(int l, int r) {
ll num = suf[l] - (r < n - 1 ? suf[r + 1] : 0);
num = (num + MOD) % MOD;
num = (num * inv[n - 1 - r]) % MOD;
return num;
}
bool same(int l1, int r1, int l2, int r2) {
if (l1 < 0 || r1 >= n || l2 < 0 || r2 >= n) return 0;
return getPRF(l1, r1) == getSUF(l2, r2);
}
ll solve(ll i, int startL = -1000, int startR = -1000) {
int sl = i / 2, sr = i / 2;
if (i % 2 != 0) sr = i / 2 + 1;
if (startL != -1000) {
sl = startL;
sr = startR;
}
if (sl < 0 || sr >= n) return 0;
int l = 0, r = min(i / 2, n - i / 2) + 2;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (same(sl - mid, sl, sr, sr + mid)) l = mid;
else r = mid;
}
return l;
}
void updateF(int l, int r) {
if (l > r) return;
sgtF.update(1, 0, n - 1, l, r);
}
void updateB(int l, int r) {
if (n - r - 1 > n - l - 1) return;
sgtB.update(1, 0, n - 1, n - r - 1, n - l - 1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precalc();
cin >> s;
n = s.size();
F[0] = 1;
for (int i = 1; i <= n; i++) F[i] = (F[i - 1] * 29) % MOD;
for (int i = 0; i < n; i++) {
if (i) prf[i] = prf[i - 1];
prf[i] = (prf[i] + (s[i] - 'a') * F[i]) % MOD;
}
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) suf[i] = suf[i + 1];
suf[i] = (suf[i] + (s[i] - 'a') * F[n - 1 - i]) % MOD;
}
ll ans = 0;
for (int i = 0; i < 2 * n - 1; i++) {
int sl = i / 2, sr = i / 2;
if (i % 2 != 0) sr = i / 2 + 1;
ll add = s[sl] == s[sr];
ll lp = solve(i) + add;
int LR = sl - (lp - 1), RR = sr + (lp - 1);
ans += lp;
if (LR != RR) {
updateF(LR, sl - (i % 2 == 0));
updateB(sr + (sl == sr), RR);
}
int L = sl - lp, R = sr + lp;
if (L < 0 || R > n - 1) continue;
ll newLp = solve(i, L - 1, R + 1);
if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1;
else add = 0;
change[L][s[R] - 'a'] += newLp + 1 + add;
newLp = solve(i, L - 1, R + 1);
if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1;
else add = 0;
change[R][s[L] - 'a'] += newLp + 1 + add;
}
sgtF.get(1, 0, n - 1, 1);
sgtB.get(1, 0, n - 1, 0);
ll mx = 0;
for (int i = 0; i < n; i++) {
ll best = 0;
for (int j = 0; j < 26; j++) best = max(best, change[i][j]);
mx = max(mx, best - a[i]);
}
cout << ans + mx;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20060 KB |
Output is correct |
| 2 |
Correct |
11 ms |
20060 KB |
Output is correct |
| 3 |
Correct |
8 ms |
20036 KB |
Output is correct |
| 4 |
Correct |
8 ms |
20060 KB |
Output is correct |
| 5 |
Correct |
9 ms |
19984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
21084 KB |
Output is correct |
| 2 |
Correct |
13 ms |
21084 KB |
Output is correct |
| 3 |
Correct |
12 ms |
21084 KB |
Output is correct |
| 4 |
Correct |
13 ms |
20572 KB |
Output is correct |
| 5 |
Correct |
11 ms |
21072 KB |
Output is correct |
| 6 |
Correct |
12 ms |
21084 KB |
Output is correct |
| 7 |
Correct |
11 ms |
21084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
43824 KB |
Output is correct |
| 2 |
Correct |
177 ms |
43604 KB |
Output is correct |
| 3 |
Correct |
143 ms |
43604 KB |
Output is correct |
| 4 |
Correct |
103 ms |
43604 KB |
Output is correct |
| 5 |
Correct |
120 ms |
43844 KB |
Output is correct |
| 6 |
Correct |
112 ms |
43940 KB |
Output is correct |
| 7 |
Correct |
105 ms |
43604 KB |
Output is correct |
| 8 |
Correct |
134 ms |
23380 KB |
Output is correct |
| 9 |
Correct |
115 ms |
43604 KB |
Output is correct |
| 10 |
Correct |
109 ms |
43604 KB |
Output is correct |
| 11 |
Correct |
167 ms |
43748 KB |
Output is correct |
| 12 |
Correct |
157 ms |
43796 KB |
Output is correct |
| 13 |
Correct |
138 ms |
43660 KB |
Output is correct |
| 14 |
Correct |
108 ms |
43720 KB |
Output is correct |
| 15 |
Correct |
114 ms |
43604 KB |
Output is correct |
| 16 |
Correct |
195 ms |
43608 KB |
Output is correct |
| 17 |
Correct |
106 ms |
43668 KB |
Output is correct |
| 18 |
Correct |
114 ms |
43720 KB |
Output is correct |
| 19 |
Correct |
99 ms |
43604 KB |
Output is correct |
