#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
// #include "debugging.hpp"
using namespace std;
/** sauce: 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 = 5;
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;
}
long long hash(int from, int to, const pair<int, char>& rep) {
long long pref = p_hash[to + 1] - p_hash[from];
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};
int last_true(int lo, int hi, function<bool(int)> check) {
int valid = -1;
while (lo <= hi) {
// cout << lo << ' ' << hi << endl;
int mid = (lo + hi) / 2;
if (check(mid)) {
lo = mid + 1;
valid = mid;
} else {
hi = mid - 1;
}
}
return valid;
}
/**
* https://oj.uz/problem/view/COI16_palinilap
* baccb should output 9
* slavko should output 7
*/
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);
auto is_pal = [&] (int from, int to) {
return h_str.hash(from, to)
== h_rev_str.hash(len - to - 1, len - from - 1);
};
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>> change_inc(len);
long long init_amt = 0;
for (int c = 0; c < len; c++) {
int most = min(c, len - c - 1);
check = [&] (int d) { return is_pal(c - d, c + d); };
int raw_pal = last_true(0, most, check);
init_amt += raw_pal + 1;
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) {
change_inc[rep.first][rep.second] += rep_pal - raw_pal;
change_inc[c - raw_pal - 1][str[c + raw_pal + 1]] += rep_pal - raw_pal;
}
// printf("%i: %i %i\n", c, raw_pal, rep_pal);
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;
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) {
change_inc[rep.first][rep.second] += rep_pal - raw_pal;
change_inc[c - raw_pal][str[c + raw_pal + 1]] += rep_pal - raw_pal;
}
// printf("%i %i: %i %i\n", c, c + 1, raw_pal, rep_pal);
}
}
long long max_inc = 0;
for (const map<char, long long>& c : change_inc) {
for (const auto& [_, i] : c) {
max_inc = max(max_inc, i);
}
}
cout << init_amt + max_inc << endl;
}
Compilation message
palinilap.cpp: In constructor 'HashedString::HashedString(const string&)':
palinilap.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
14596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
