#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
class HASH {
int mod, base;
vector<int> p = {1} , hashes = {0};
int mul(int a , int b) {
return a * 1ll * b % mod;
}
int add(int a , int b) {
a += b;
while (a >= mod) a -= mod;
while (a < 0) a += mod;
return a;
}
public:
HASH(int _mod , int _base) : mod(_mod), base(_base) {}
void push_back(int x) {
hashes.push_back(add(mul(hashes.back() , base) , x));
p.push_back(mul(p.back() , base));
}
int get(int l , int r) {
assert(r + 1 < hashes.size());
return add(hashes[r + 1] , -mul(p[r - l + 1] , hashes[l]));
}
};
struct D_HASH {
const int B1 = 256;
const int B2 = 128;
const int M1 = 1e9 + 7;
const int M2 = 1e9 + 9;
array<HASH , 2> h;
D_HASH() : h{HASH(M1 , B1) , HASH(M2 , B2)} {}
D_HASH(string str) : h{HASH(M1, B1), HASH(M2, B2)} {
for (char c : str) {
push_back(c);
}
}
void push_back(int x) { // x != 0
h[0].push_back(x);
h[1].push_back(x);
}
array<int , 2> get(int l , int r) { // send zero based
assert(l <= r);
return {h[0].get(l , r) , h[1].get(l , r)};
};
};
string rev (string s) {
string t = s;
reverse(t.begin() , t.end());
return t;
}
enum {odd , even};
const int N = 1e5 + 5;
int first[N][2] , second[N][2];
long long New[N][26];
long long sub[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string str;
cin >> str;
int n = str.size();
D_HASH h(str) , rh(rev(str));
auto same = [&](int l , int r , int s , int e) {
if (l < 0 || e >= n)
return false;
return h.get(l , r) == rh.get(n - e - 1, n - s - 1); // reverse one
};
for (int i = 0 ;i < n ;i++) {
int l = 1 , r = n;
// even
while (l <= r) {
int mid = (l + r) / 2;
if (same(i - mid , i - 1 , i , i + mid - 1)) {
first[i][even] = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
int e = i - first[i][even] - 2;
int s = i + first[i][even] + 1;
l = 1 , r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (same(e - mid + 1 , e , s , s + mid - 1)) {
second[i][even] = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// odd
l = 1 , r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (same(i - mid + 1 , i , i , i + mid - 1)) {
first[i][odd] = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
e = i - first[i][odd] - 1 , s = i + first[i][odd] + 1;
l = 1 , r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (same(e - mid + 1 , e , s , s + mid - 1)) {
second[i][odd] = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
int t = i - first[i][even] - 1 , tt = i + first[i][even];
if (t >= 0 && tt < n) {
New[tt][str[t] - 'a'] += second[i][even] + 1;
New[t][str[tt] - 'a'] += second[i][even] + 1;
}
t = i - first[i][odd] , tt = i + first[i][odd];
if (t >= 0 && tt < n) {
New[tt][str[t] - 'a'] += second[i][odd] + 1;
New[t][str[tt] - 'a'] += second[i][odd] + 1;
}
}
int active = 0;
long long pal = 0;
vector<int> en(n);
for (int i = 0 ;i < n ;i++) {
if (first[i][even]) {
active++;
pal += first[i][even];
en[i + first[i][even] - 1]++;
}
sub[i] += pal;
active++;
pal += first[i][odd];
en[i + first[i][odd] - 1]++;
pal -= active;
active -= en[i];
}
active = 0 , pal = 0;
fill(en.begin() , en.end() , 0);
for (int i = n - 1 ;i >= 0 ;i--) {
sub[i] += pal;
active++;
pal += first[i][odd];
en[i - first[i][odd] + 1]++;
pal -= active;
active -= en[i];
if (first[i][even]) {
active++;
pal += first[i][even];
en[i - first[i][even]]++;
}
}
long long pals = 0 , mx = 0;
for (int i = 0 ;i < n ;i++) {
pals += first[i][odd] + first[i][even];
for (int j = 0 ;j < 26 ;j++)
mx = max(mx , New[i][j] - sub[i]);
}
cout << pals + mx;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from palinilap.cpp:5:
palinilap.cpp: In member function 'int HASH::get(int, int)':
palinilap.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | assert(r + 1 < hashes.size());
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1772 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1248 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
392 ms |
27256 KB |
Output is correct |
| 2 |
Correct |
203 ms |
26464 KB |
Output is correct |
| 3 |
Correct |
218 ms |
26464 KB |
Output is correct |
| 4 |
Correct |
377 ms |
27360 KB |
Output is correct |
| 5 |
Correct |
380 ms |
27232 KB |
Output is correct |
| 6 |
Correct |
375 ms |
27232 KB |
Output is correct |
| 7 |
Correct |
380 ms |
27232 KB |
Output is correct |
| 8 |
Correct |
121 ms |
6112 KB |
Output is correct |
| 9 |
Correct |
380 ms |
27232 KB |
Output is correct |
| 10 |
Correct |
380 ms |
27360 KB |
Output is correct |
| 11 |
Correct |
200 ms |
26812 KB |
Output is correct |
| 12 |
Correct |
379 ms |
27232 KB |
Output is correct |
| 13 |
Correct |
358 ms |
27232 KB |
Output is correct |
| 14 |
Correct |
379 ms |
27360 KB |
Output is correct |
| 15 |
Correct |
394 ms |
27232 KB |
Output is correct |
| 16 |
Correct |
245 ms |
26848 KB |
Output is correct |
| 17 |
Correct |
369 ms |
27232 KB |
Output is correct |
| 18 |
Correct |
393 ms |
27232 KB |
Output is correct |
| 19 |
Correct |
377 ms |
27232 KB |
Output is correct |
