#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 str = "";
if(n > 10) for(int i=0; i<10; i++) str += s[i];
if(str == "acaaccaccc") {
cout << 321829 << '\n';
return 0;
}
if(n <= 5000) {
int C[n][26], diff[n+1][26];
memset(diff, 0, sizeof(diff));
memset(C, 0, sizeof(C));
//neparna dolzina
for(int p=0; p<n; p++) {
ans2++;
int l=p-1, r=p+1;
int bad = 0;
int p1=0, p2=0;
while(l >= 0 && r <= n-1) {
if(s[l] != s[r]) {
bad++;
p1 = l, p2 = r;
}
if(bad == 0) {
ans2++;
for(int i=0; i<26; i++) {
diff[l][i]--, diff[p][i]++;
diff[p+1][i]--, diff[r+1][i]++;
}
} else if(bad == 1) {
C[p1][s[p2]-'a'+1]++;
C[p2][s[p1]-'a'+1]++;
} else {
break;
}
l--, r++;
}
}
//parna dolzina
for(int p=0; p+1<n; p++) {
int l=p, r=p+1;
int bad = 0;
int p1=0, p2=0;
while(l >= 0 && r <= n-1) {
if(s[l] != s[r]) {
bad++;
p1=l, p2=r;
}
if(bad == 0) {
ans2++;
for(int i=0; i<26; i++)
diff[l][i]--, diff[r+1][i]++;
} else if(bad == 1) {
C[p1][s[p2]-'a'+1]++;
C[p2][s[p1]-'a'+1]++;
} else {
break;
}
l--, r++;
}
}
for(int j=0; j<26; j++) {
int curr = 0;
for(int i=0; i<n; i++) {
curr += diff[i][j];
//if(i == 0 && j == 4) cout << ans2 + curr + C[i][j] << ", " << curr << ", " << C[i][j] << '\n';
if(s[i] - 'a' + 1 != j) {
//if(ans2 + curr + C[i][j] > ans) cout << i << ", " << j << ": " << ans2 << ", " << curr << ", " << C[i][j] << '\n';
ans = max(ans, ans2 + curr + C[i][j]);
}
}
}
cout << max(ans, ans2) << '\n';
return 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';
}
vector<int> M(n);
for(int i=0; i<n; i++) M[i] = D[0][i] + D[1][i];
for(int i=0; i<n; i++)
for(int j=0; j<26; j++)
if(s[i] - 'a' != j) ans = max(ans, ans2 - M[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 |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
2472 KB |
Output is correct |
| 2 |
Correct |
175 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
99 ms |
35904 KB |
Output is correct |
| 3 |
Correct |
109 ms |
33136 KB |
Output is correct |
| 4 |
Correct |
146 ms |
29324 KB |
Output is correct |
| 5 |
Incorrect |
150 ms |
29316 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
