#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
struct Hash {
int n;
string s;
const ll p = 31, mod = 1e9 + 7;
vector<ll> pw, hash;
Hash(string _s) : s(_s) {
n = s.size();
pw.resize(n+1);
hash.resize(n+1);
pw[0] = 1;
for(int i=1; i<=n; i++) pw[i] = (pw[i-1] * p) % mod;
hash[0] = s[0] - 'a' + 1;
for(int i=1; i<n; i++) hash[i] = (hash[i-1] + pw[i] * (s[i] - 'a' + 1)) % mod;
}
ll getHash(int l, int r) { return (hash[r] - (l ? hash[l-1] : 0) + mod) % mod; }
ll getHash(int l, int r, int p, char ch) {
ll ans = getHash(l, r);
ans = (ans + pw[p] * (ch - 'a' + 1) - pw[p] * (s[p] - 'a' + 1) + mod) % mod;
return ans;
}
bool equal(int l1, int r1, int l2, int r2) {
if(r1 - l1 != r2 - l2) return 0;
if(l1 > l2) swap(l1, l2), swap(r1, r2);
return (pw[l2-l1] * getHash(l1, r1) % mod) == getHash(l2, r2);
}
bool isPal(int l, int r) {
return equal(l, r, n-1-r, n-1-l);
}
bool isPal(int l, int r, int p, char ch) {
int l2=n-1-r, r2=n-1-l;
ll h1 = getHash(l, r, p, ch);
ll h2 = getHash(n-1-r, n-1-l, n-1-p, ch);
return (pw[l2-l] * h1 % mod) == h2;
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
int n = s.size();
ll ans = 0, ans2 = 0;
string s2 = s; reverse(s2.begin(), s2.end());
s += s2;
Hash H(s);
//neparna dolzina
int C[n][26], D[2][n+1];
memset(C, 0, sizeof(C));
memset(D, 0, sizeof(D));
vector<pair<int, int> > R[2];
for(int i=0; i<n; i++) {
int L = min(i, n-1-i);
int l=0, r=L, len=0;
while(l <= r) {
int mid = (l + r) / 2;
if(H.isPal(i-mid, i+mid)) len = mid, l = mid + 1;
else r = mid - 1;
}
if(len) {
R[0].push_back({ i - len, i - 1 });
//cout << "remove left " << i - len << " " << i-1 << '\n';
R[1].push_back({ i + 1, i + len });
//cout << "remove right " << i+1 << " " << i+len << '\n';
}
//cout << i << ": " << len << '\n';
if(i - len - 1 >= 0 && i + len + 1 < n) {
l=len+1, r=L;
int len2=0;
while(l <= r) {
int mid = (l + r) / 2;
if(H.isPal(i-mid, i+mid, i-len-1, s[i+len+1])) len2 = mid, l = mid + 1;
else r = mid - 1;
}
//cout << len2 << '\n';
//cout << "add " << len2 - len << " on " << i-len-1 << " " << i+len+1 << '\n';
C[i-len-1][s[i+len+1]-'a'] += len2 - len;
C[i+len+1][s[i-len-1]-'a'] += len2 - len;
}
ans2 += len + 1;
}
for(int i=0; i<n-1; i++) {
int L = min(i, n-2-i);
int l=0, r=L, len=0;
while(l <= r) {
int mid = (l + r) / 2;
if(H.isPal(i-mid, i+1+mid)) len = mid, l = mid + 1;
else r = mid - 1;
}
//cout << i << ": " << len << '\n';
if(H.isPal(i, i+1)) {
R[0].push_back({ i - len, i });
//cout << "remove left " << i-len << " " << i << '\n';
R[1].push_back({ i + 1, i + len + 1 });
//cout << "remove right " << i+1 << " " << i+len+1 << '\n';
if(i-len-1 >= 0 && i+len+2 < n) {
l=len+1, r=L;
int len2 = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(H.isPal(i-mid, i+mid+1, i-len-1, s[i+len+2])) len2 = mid, l = mid + 1;
else r = mid - 1;
}
//cout << len2 << " (0)" << '\n';
//cout << "add " << len2 - len << " on " << i-len-1 << " " << i+len+2 << '\n';
C[i-len-1][s[i+len+2]-'a'] += len2 - len;
C[i+len+2][s[i-len-1]-'a'] += len2 - len;
}
ans2 += len + 1;
} else {
l=0, r=L;
int len2=0;
while(l <= r) {
int mid = (l + r) / 2;
if(H.isPal(i-mid, i+mid+1, i, s[i+1])) len2 = mid, l = mid + 1;
else r = mid - 1;
}
//cout << len2 << " (1)" << '\n';
//cout << "add " << len2 + 1 << " on " << i << " " << i+1 << '\n';
C[i][s[i+1]-'a'] += len2 + 1;
C[i+1][s[i]-'a'] += len2 + 1;
}
}
for(int i=0; i<2; i++) {
if(i == 1) for(auto &x : R[i]) x = { n - x.second - 1, n - x.first - 1};
//for(auto &x : R[i]) cout << x.first << " " << x.second << '\n';
for(auto &x : R[i]) D[i][x.first]++, D[i][x.second+1]--;
for(int j=1; j<=n; j++) D[i][j] += D[i][j-1];
for(auto &x : R[i]) D[i][x.second+1] -= x.second - x.first + 1;
for(int j=1; j<=n; j++) D[i][j] += D[i][j-1];
if(i) reverse(D[i], D[i] + n);
//for(int j=0; j<n; j++) cout << D[i][j] << " ";
//cout << '\n';
}
for(int i=0; i<n; i++)
for(int j=0; j<26; j++)
if(s[i] - 'a' != j) ans = max(ans, ans2 - D[0][i] - D[1][i] + C[i][j]);
cout << max(ans, ans2) << '\n';
return 0;
}
Compilation message
palinilap.cpp: In member function 'bool Hash::isPal(long long int, long long int, long long int, char)':
palinilap.cpp:44:23: warning: unused variable 'r2' [-Wunused-variable]
44 | int l2=n-1-r, r2=n-1-l;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
29564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
