#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
// BeginCodeSnip{String Hashing}
/** source: https://usaco.guide/gold/modular */
long long pow_mod(long long x, long long n, long long mod) {
assert(n >= 0);
x %= mod;
long long res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % mod; }
x = x * x % mod;
n /= 2;
}
return res;
}
class HashedString {
private:
static const long long MOD = 1e9 + 9;
static const long long POW = 101;
static vector<long long> pow;
static vector<long long> mod_inv;
const string &s;
vector<long long> p_hash;
public:
HashedString(const string &s) : s(s), p_hash(s.size() + 1) {
while (pow.size() < s.size()) {
pow.push_back((pow.back() * POW) % MOD);
mod_inv.push_back(pow_mod(pow.back(), MOD - 2, MOD));
}
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = (p_hash[i] + s[i] * pow[i] % MOD) % MOD;
}
}
long long hash(int from, int to) {
long long pref = (p_hash[to + 1] - p_hash[from] + MOD) % MOD;
return pref * mod_inv[from] % MOD;
}
/** @return substring hash with a given character replaced */
long long hash(int from, int to, const pair<int, char> &rep) {
long long pref = p_hash[to + 1] - p_hash[from];
if (from <= rep.first && rep.first <= to) {
pref += rep.second * pow[rep.first] - s[rep.first] * pow[rep.first];
}
return (pref % MOD + MOD) * mod_inv[from] % MOD;
}
};
vector<long long> HashedString::pow = {1};
vector<long long> HashedString::mod_inv = {1};
// EndCodeSnip
/**
* @return the largest number in [lo, hi] such that check is satisfied.
* if no number in the range works, -1 is returned
*/
int last_true(int lo, int hi, function<bool(int)> check) {
int valid = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) {
lo = mid + 1;
valid = mid;
} else {
hi = mid - 1;
}
}
return valid;
}
/**
* @return the resulting array when the operations in the ranges are performend
* @param ranges in each of the ranges in this variable, consecutive numbers
* starting from 1 are added to the subarray. for example, [0, 3] would add
* the numbers 1, 2, 3, and 4 to the first 4 elements to the range [0, 3].
*/
vector<long long> range_res(int size, const vector<pair<int, int>> &ranges) {
vector<long long> arr(size + 1);
for (const auto &[a, b] : ranges) {
arr[a]++;
arr[b + 1]--;
}
for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
for (const auto &[a, b] : ranges) { arr[b + 1] -= b - a + 1; }
for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
arr.pop_back();
return arr;
}
int main() {
string str;
cin >> str;
int len = str.size(); // shorthand
string rev_str = str;
reverse(rev_str.begin(), rev_str.end());
HashedString h_str(str), h_rev_str(rev_str);
// checks if a substring is a palindrome
auto is_pal = [&](int from, int to) {
return h_str.hash(from, to) == h_rev_str.hash(len - to - 1, len - from - 1);
};
// checks if a substring is a palindrome with a replaced character
auto is_pal_rep = [&](int from, int to, pair<int, char> rep) {
pair<int, char> r_rep{len - rep.first - 1, rep.second};
return h_str.hash(from, to, rep) ==
h_rev_str.hash(len - to - 1, len - from - 1, r_rep);
};
function<bool(int)> check;
vector<map<char, long long>> good(len);
// the ranges we have to add to our bad array
vector<pair<int, int>> removal1, removal2;
long long init_amt = 0; // the initial amount of palindromes
for (int c = 0; c < len; c++) {
// first check the odd-length palindromes relative to c
int most = min(c, len - c - 1); // the most we can extend from position c
check = [&](int d) { return is_pal(c - d, c + d); };
int raw_pal = last_true(0, most, check);
init_amt += raw_pal + 1;
if (raw_pal > 0) {
removal1.push_back({c - raw_pal, c - 1});
removal2.push_back({c + 1, c + raw_pal});
}
pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal - 1]};
check = [&](int d) { return is_pal_rep(c - d, c + d, rep); };
int rep_pal = last_true(raw_pal + 1, most, check);
if (rep_pal != -1) {
good[rep.first][rep.second] += rep_pal - raw_pal;
good[c - raw_pal - 1][str[c + raw_pal + 1]] += rep_pal - raw_pal;
}
// and then the even-length palindromes
if (c < len - 1) {
int most = min(c + 1, len - c - 1);
check = [&](int d) { return is_pal(c - d + 1, c + d); };
int raw_pal = last_true(0, most, check);
init_amt += raw_pal;
if (raw_pal > 0) {
removal1.push_back({c - raw_pal + 1, c});
removal2.push_back({c + 1, c + raw_pal});
}
pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal]};
check = [&](int d) { return is_pal_rep(c - d + 1, c + d, rep); };
int rep_pal = last_true(raw_pal + 1, most, check);
if (rep_pal != -1) {
good[rep.first][rep.second] += rep_pal - raw_pal;
good[c - raw_pal][str[c + raw_pal + 1]] += rep_pal - raw_pal;
}
}
}
for (pair<int, int> &r : removal2) { r = {len - r.second - 1, len - r.first - 1}; }
// these two combined give the bad array stated in the analysis
vector<long long> bad1 = range_res(len, removal1);
vector<long long> bad2 = range_res(len, removal2);
std::reverse(bad2.begin(), bad2.end());
long long max_weight = init_amt;
for (int i = 0; i < len; i++) {
long long max_inc = 0;
for (const auto &[_, i] : good[i]) { max_inc = max(max_inc, i); }
max_weight = max(max_weight, init_amt + max_inc - bad1[i] - bad2[i]);
}
cout << max_weight << endl;
}
Compilation message
palinilap.cpp: In constructor 'HashedString::HashedString(const string&)':
palinilap.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1104 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1360 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1360 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
17664 KB |
Output is correct |
| 2 |
Correct |
82 ms |
20484 KB |
Output is correct |
| 3 |
Correct |
86 ms |
20484 KB |
Output is correct |
| 4 |
Correct |
123 ms |
23308 KB |
Output is correct |
| 5 |
Correct |
120 ms |
22800 KB |
Output is correct |
| 6 |
Correct |
134 ms |
22628 KB |
Output is correct |
| 7 |
Correct |
132 ms |
23308 KB |
Output is correct |
| 8 |
Correct |
63 ms |
14356 KB |
Output is correct |
| 9 |
Correct |
137 ms |
22540 KB |
Output is correct |
| 10 |
Correct |
118 ms |
22540 KB |
Output is correct |
| 11 |
Correct |
85 ms |
20484 KB |
Output is correct |
| 12 |
Correct |
115 ms |
20484 KB |
Output is correct |
| 13 |
Correct |
110 ms |
18700 KB |
Output is correct |
| 14 |
Correct |
126 ms |
24076 KB |
Output is correct |
| 15 |
Correct |
116 ms |
23048 KB |
Output is correct |
| 16 |
Correct |
106 ms |
26680 KB |
Output is correct |
| 17 |
Correct |
137 ms |
33644 KB |
Output is correct |
| 18 |
Correct |
137 ms |
17420 KB |
Output is correct |
| 19 |
Correct |
146 ms |
33804 KB |
Output is correct |
