#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 5005;
const int Alph = 26;
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 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 ans;
ll initPalindrome[maxN][maxN], oddPalindrome[maxN];
ll diffChar[maxN][maxN], diagDiff[maxN][maxN];
ll change[maxN][Alph];
void computeInitial() {
for (int i = 1; i <= n; i++) {
HashString H = HashString();
for (int j = i; j <= n; j++) {
H = H + HashString(S[j]);
initPalindrome[i][j] = H.isPalindrome();
ans += initPalindrome[i][j];
}
}
// compute odd palindromes whose center is i
for (int c = 1; c <= n; c++) {
for (int d = 0; c-d >= 1 && c+d <= n; d++) {
oddPalindrome[c] += initPalindrome[c-d][c+d];
}
}
// compute some sort of prefsum for initPalindrome
for (int i = 1; i <= n; i++) {
for (int j = n; j >= 1; j--) {
initPalindrome[i][j] += initPalindrome[i-1][j] + initPalindrome[i][j+1] - initPalindrome[i-1][j+1];
}
}
// calculate whether characters at (i, j) are different or not
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
diffChar[i][j] = (S[i] != S[j]);
}
}
// also calculate some sort of diagonal sum
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
diagDiff[i][j] = diagDiff[i-1][j+1] + diffChar[i][j];
//cout << diagDiff[i][j] << ' ';
}
//cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> S;
n = S.length();
S = "#" + S;
precomp();
computeInitial();
// find for each substring l..r, on which character can it be changed so that it can be a palindrome
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
ll total = diagDiff[r][l] - diagDiff[l-1][r+1];
if (total != 2) continue;
//cout << l << ' ' << r << '\n';
// binary search different position
int _L = l, _R = r, dpos = -1;
while (_L <= _R) {
int _M = (_L + _R) >> 1;
if (diagDiff[_M][l+r-_M] - diagDiff[l-1][r+1] >= 1) {
dpos = _M;
_R = _M - 1;
} else {
_L = _M + 1;
}
}
if (dpos == -1) {cout << "!!!\n";}
// insert to change array
int dpos2 = l+r-dpos;
change[dpos][S[dpos2] - 'a']++;
change[dpos2][S[dpos] - 'a']++;
//for (ll i = l; i <= r; i++) {cout << S[i];}
//cout << '\n';
}
}
// finally, compute each possible action that we can take
ll maxDiff = 0;
for (int i = 1; i <= n; i++) {
for (int nw = 0; nw < Alph; nw++) {
//cout << "change[" << i << "][" << nw << "] = " << change[i][nw] << '\n';
if (nw == S[i] - 'a') continue;
// remove all palindromes with that character as a component, except for odd palindromes
ll delta = -initPalindrome[i][i] + oddPalindrome[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:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
16 | if (!x) return 0; if (!y) return 1;
| ^~
palinilap.cpp:16:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
16 | if (!x) return 0; if (!y) return 1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
395 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
