#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxN = 1e5 + 5;
const ll Alph = 26;
#ifdef Zanite
#define debug(x) cout << #x << " = " << x << '\n'
#else
#define debug(x)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);}
const ll mod = 1049433169;
ll madd(ll x, ll y) {x += y; if (x >= mod) x -= mod; return x;}
ll msub(ll x, ll y) {x -= y; if (x < 0) x += mod; return x;}
ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}
ll modexp(ll x, ll y) {
if (!x) return 0; if (!y) return 1;
ll t = modexp(x, y >> 1);
return mmul(t, mmul(t, ((y & 1ll) ? x : 1)));
}
ll key;
ll kpow[maxN], invkpow[maxN];
ll n;
void precomp() {
key = getRand(1e5, 2e5);
kpow[0] = invkpow[0] = 1;
kpow[1] = key, invkpow[1] = modexp(key, mod-2);
for (ll i = 1; i <= n; i++) {
kpow[i] = mmul(kpow[i-1], kpow[1]);
invkpow[i] = mmul(invkpow[i-1], invkpow[1]);
}
}
struct HashString {
ll fwd, bwd, len;
HashString() {fwd = bwd = len = 0;}
HashString(char c) {
fwd = bwd = c - 'a';
len = 1;
}
HashString operator + (const HashString &other) const {
HashString ret = HashString();
ret.fwd = madd(fwd, mmul(other.fwd, kpow[len]));
ret.bwd = madd(mmul(bwd, kpow[other.len]), other.bwd);
ret.len = len + other.len;
return ret;
}
bool isPalindrome() {return (fwd == bwd);}
};
string S;
ll fwd[maxN], bwd[maxN];
ll odd[maxN], even[maxN];
ll change[maxN][Alph];
ll intersect[maxN];
ll getFwd(ll l, ll r) {return mmul(invkpow[l-1], msub(fwd[r], fwd[l-1]));}
ll getBwd(ll l, ll r) {return mmul(invkpow[n-r], msub(bwd[l], bwd[r+1]));}
void computeInitial() {
// compute forwards and backwards hash
for (ll i = 1; i <= n; i++) {
fwd[i] = madd(fwd[i-1], mmul(S[i] - 'a', kpow[i-1]));
}
for (ll i = n; i >= 1; i--) {
bwd[i] = madd(bwd[i+1], mmul(S[i] - 'a', kpow[n-i]));
}
// find the number of odd and even palindromes centered at i
// for even palindromes, the index is the "left part of center"
// compute intersect[i] := the number of polygons that involve character i
// because we add slopes, this can be done with prefix prefix difference
// also, for each center, find the first differing character
// and find how many palindromes can be created by changing that character
// odd
for (ll i = 1; i <= n; i++) {
ll l = 0, r = min(i-1, n-i), ans = -1;
while (l <= r) {
ll m = (l+r) >> 1;
if (getFwd(i-m, i+m) == getBwd(i-m, i+m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
odd[i] = ans+1;
intersect[i-ans]++;
intersect[i+1] -= 2;
intersect[i+ans+2]++;
// first different
ll DL = i-ans-1, DR = i+ans+1;
if (DL < 1 || DR > n) continue;
// extend palindrome
l = 1, r = min(DL-1, n-DR), ans = 0;
while (l <= r) {
ll m = (l+r >> 1);
if (getFwd(DL-m, DL-1) == getBwd(DR+1, DR+m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
change[DL][S[DR] - 'a'] += ans+1;
change[DR][S[DL] - 'a'] += ans+1;
}
// even
for (ll i = 1; i < n; i++) {
ll l = 0, r = min(i-1, n-(i+1)), ans = -1;
while (l <= r) {
ll m = (l+r) >> 1;
if (getFwd(i-m, i+m+1) == getBwd(i-m, i+m+1)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
even[i] = ans+1;
intersect[i-ans]++;
intersect[i+1]--;
intersect[i+2]--;
intersect[i+ans+3]++;
// first different
ll DL = i-ans-1, DR = i+ans+2;
if (DL < 1 || DR > n) continue;
// extend palindrome
l = 1, r = min(DL-1, n-DR), ans = 0;
while (l <= r) {
ll m = (l+r >> 1);
if (getFwd(DL-m, DL-1) == getBwd(DR+1, DR+m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
change[DL][S[DR] - 'a'] += ans+1;
change[DR][S[DL] - 'a'] += ans+1;
}
// restore the slope slope array as slope array and then as the array
for (ll i = 1; i <= 2; i++) {
for (ll j = 1; j < maxN; j++) {
intersect[j] += intersect[j-1];
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> S;
n = S.length();
S = "#" + S;
precomp();
computeInitial();
// calculate answer if we don't change anything
ll ans = 0;
for (ll i = 1; i <= n; i++) {
ans += odd[i] + even[i];
}
debug(ans);
// compute each possible action that we can take
ll maxDiff = 0;
for (ll i = 1; i <= n; i++) {
for (ll nw = 0; nw < Alph; nw++) {
if (nw == S[i] - 'a') continue;
// remove all palindromes with that character as a component, except for odd palindromes
ll delta = -intersect[i] + odd[i];
// add all palindromes that will be created
delta += change[i][nw];
maxDiff = max(maxDiff, delta);
}
}
cout << ans + maxDiff << '\n';
}
Compilation message
palinilap.cpp: In function 'll modexp(ll, ll)':
palinilap.cpp:23:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
23 | if (!x) return 0; if (!y) return 1;
| ^~
palinilap.cpp:23:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if (!x) return 0; if (!y) return 1;
| ^~
palinilap.cpp: In function 'void computeInitial()':
palinilap.cpp:115:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | ll m = (l+r >> 1);
| ~^~
palinilap.cpp:153:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
153 | ll m = (l+r >> 1);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
26268 KB |
Output is correct |
| 2 |
Correct |
37 ms |
26352 KB |
Output is correct |
| 3 |
Correct |
37 ms |
26384 KB |
Output is correct |
| 4 |
Correct |
48 ms |
26284 KB |
Output is correct |
| 5 |
Correct |
52 ms |
26372 KB |
Output is correct |
| 6 |
Correct |
48 ms |
26260 KB |
Output is correct |
| 7 |
Correct |
61 ms |
26352 KB |
Output is correct |
| 8 |
Correct |
33 ms |
6004 KB |
Output is correct |
| 9 |
Correct |
72 ms |
26248 KB |
Output is correct |
| 10 |
Correct |
47 ms |
26292 KB |
Output is correct |
| 11 |
Correct |
39 ms |
26356 KB |
Output is correct |
| 12 |
Correct |
46 ms |
26272 KB |
Output is correct |
| 13 |
Correct |
52 ms |
26340 KB |
Output is correct |
| 14 |
Correct |
58 ms |
26296 KB |
Output is correct |
| 15 |
Correct |
68 ms |
26256 KB |
Output is correct |
| 16 |
Correct |
42 ms |
26292 KB |
Output is correct |
| 17 |
Correct |
49 ms |
26292 KB |
Output is correct |
| 18 |
Correct |
56 ms |
26352 KB |
Output is correct |
| 19 |
Correct |
54 ms |
26308 KB |
Output is correct |
