#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int M=1e9+696969;
const ar<int, 2> B={129, 7282};
ar<int, 2> operator+ (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
if ((a[i] += b[i]) >= M)
a[i] -= M;
return a;
}
ar<int, 2> operator- (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
if ((a[i] -= b[i]) < 0)
a[i] += M;
return a;
}
ar<int, 2> operator* (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
a[i] = (ll)a[i] * b[i] % M;
return a;
}
ar<int, 2> mk(char c) {
return {c, c};
}
const int mxN=1e5;
int n, d1[mxN], d2[mxN];
string s;
ar<int, 2> p[mxN], h1[mxN+1], h2[mxN+1];
ll bad[mxN], pref[mxN], change[26][mxN];
vector<ar<int, 2>> cands[mxN][26];
ar<int, 2> get1(int l, int r, ar<int, 2> change={}) {
return h1[r+1]-h1[l]*p[r-l+1]+change;
}
ar<int, 2> get2(int l, int r, ar<int, 2> change={}) {
return h2[l]-h2[r+1]*p[r-l+1]+change;
}
bool ck(int l, int r, int i=-1, ar<int, 2> change={}) {
assert(0<=l&&l<=r&&r<n);
if (i<l||i>r)
return get1(l, r)==get2(l, r);
return get1(l, r)+change*p[r-i]==get2(l, r)+change*p[i-l];
}
int solve1(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]
assert(0<=i&&i<n);
int lb=1, rb=min(i+1, n-i);
while(lb<rb) {
int mid=(lb+rb+1)/2;
if (ck(i-mid+1, i+mid-1, pos, change))
lb=mid;
else
rb=mid-1;
}
return lb;
}
int solve2(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]-s[i+1]
assert(0<=i&&i<n-1);
//if (s[i]!=s[i+1]&&pos==-1)
// return 0;
int lb=0, rb=min(i+1, n-1-i);
while(lb<rb) {
int mid=(lb+rb+1)/2;
if (ck(i-mid+1, i+mid, pos, change))
lb=mid;
else
rb=mid-1;
}
return lb;
}
void add_seg(int l, int r) {
assert(0<=l&&l<=r&&r<n);
++pref[l], --pref[r+1];
bad[r+1]-=r-l+1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s, n=s.size();
p[0]={1, 1};
for (int i=1; i<n; ++i)
p[i]=p[i-1]*B;
for (int i=0; i<n; ++i)
h1[i+1]=h1[i]*B+mk(s[i]);
for (int i=n-1; ~i; --i)
h2[i]=h2[i+1]*B+mk(s[i]);
ll base=0;
for (int i=0; i<n; ++i) {
d1[i]=solve1(i);
d2[i]=i+1<n?solve2(i):0;
base+=d1[i]+d2[i];
}
for (int rep=0; rep<2; ++rep) {
for (int i=0; i<n; ++i) {
if (d1[i]>1)
add_seg(i-d1[i]+1, i-1);
if (i-d1[i]+1&&i+d1[i]<n)
cands[i-d1[i]][s[i+d1[i]]-'a'].push_back({i, 1});
}
for (int i=0; i+1<n; ++i) {
if (d2[i])
add_seg(i-d2[i]+1, i);
if (i-d2[i]+1&&i+d2[i]+1<n)
cands[i-d2[i]][s[i+d2[i]+1]-'a'].push_back({i, 2});
}
for (int i=0; i<n; ++i) {
if (i) {
pref[i]+=pref[i-1];
bad[i]+=bad[i-1];
}
bad[i]+=pref[i];
for (int j=0; j<26; ++j) {
if (s[i]=='a'+j)
continue;
change[j][i]-=bad[i];
for (auto [c, t] : cands[i][j])
change[j][i]+=t==1?solve1(c, i, mk('a'+j)-mk(s[i]))-d1[c]:solve2(c, i, mk('a'+j)-mk(s[i]))-d2[c];
}
}
reverse(d1, d1+n);
reverse(d2, d2+n-1);
for (int j=0; j<26; ++j)
reverse(change[j], change[j]+n);
memset(bad, 0, sizeof(bad));
memset(pref, 0, sizeof(pref));
for (int i=0; i<n; ++i)
for (int j=0; j<26; ++j)
cands[i][j].clear();
reverse(s.begin(), s.end());
for (int i=0; i<n; ++i)
h1[i+1]=h1[i]*B+mk(s[i]);
for (int i=n-1; ~i; --i)
h2[i]=h2[i+1]*B+mk(s[i]);
}
ll ans=base;
for (int i=0; i<26; ++i)
ans=max(ans, base+*max_element(change[i], change[i]+n));
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
63024 KB |
Output is correct |
2 |
Correct |
34 ms |
63052 KB |
Output is correct |
3 |
Correct |
31 ms |
63120 KB |
Output is correct |
4 |
Correct |
31 ms |
63128 KB |
Output is correct |
5 |
Correct |
31 ms |
63060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
64444 KB |
Output is correct |
2 |
Correct |
40 ms |
64476 KB |
Output is correct |
3 |
Correct |
45 ms |
64380 KB |
Output is correct |
4 |
Correct |
51 ms |
63948 KB |
Output is correct |
5 |
Correct |
46 ms |
64460 KB |
Output is correct |
6 |
Correct |
45 ms |
64548 KB |
Output is correct |
7 |
Correct |
44 ms |
64464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
397 ms |
90132 KB |
Output is correct |
2 |
Correct |
317 ms |
92044 KB |
Output is correct |
3 |
Correct |
236 ms |
90492 KB |
Output is correct |
4 |
Correct |
388 ms |
91336 KB |
Output is correct |
5 |
Correct |
406 ms |
91236 KB |
Output is correct |
6 |
Correct |
410 ms |
93956 KB |
Output is correct |
7 |
Correct |
416 ms |
93832 KB |
Output is correct |
8 |
Correct |
135 ms |
86608 KB |
Output is correct |
9 |
Correct |
398 ms |
91276 KB |
Output is correct |
10 |
Correct |
483 ms |
93824 KB |
Output is correct |
11 |
Correct |
336 ms |
92024 KB |
Output is correct |
12 |
Correct |
368 ms |
92764 KB |
Output is correct |
13 |
Correct |
405 ms |
90952 KB |
Output is correct |
14 |
Correct |
408 ms |
94184 KB |
Output is correct |
15 |
Correct |
406 ms |
94000 KB |
Output is correct |
16 |
Correct |
349 ms |
92428 KB |
Output is correct |
17 |
Correct |
409 ms |
98356 KB |
Output is correct |
18 |
Correct |
394 ms |
91448 KB |
Output is correct |
19 |
Correct |
401 ms |
92748 KB |
Output is correct |