#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n, md = 1e9 + 7, base = 32, pre[N], f[30][N];
vector<int> pw;
string s, rs;
struct hsh
{
vector<int> gt;
hsh(string s){
int len = (int) s.size();
while ((int) pw.size() - 1 < len){
pw.push_back(pw.back() * base % md);
}
gt.resize(len + 1, 0);
for (int i = 1; i <= len; i++){
gt[i] = (gt[i - 1] * base + s[i - 1] - 'a' + 1) % md;
}
}
int gethsh(int l, int r){
return (gt[r] - gt[l - 1] * pw[r - l + 1] + md * md) % md;
}
};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> s;
rs = s;
reverse(rs.begin(), rs.end());
pw.push_back(1);
hsh h1 = hsh(s);
hsh h2 = hsh(rs);
int n = (int) s.size();
s = " " + s;
rs = " " + rs;
int sum = 0;
for (int i = 1; i <= n; i++){
for (int j = i; j <= min(n, i + 1); j++){
int l = 1, r = min(i, n - j + 1), rt = 1;
if (s[i] == s[j]){
while (l <= r){
int mid = (l + r) >> 1;
int ps = j, ps2 = j + mid - 1;
if (h1.gethsh(i - mid + 1, i) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
rt = mid;
l = mid + 1;
}
else r = mid - 1;
}
sum += rt;
l = i - rt + 1, r = j + rt - 1;
if (i != j){
pre[l] += 1;
pre[r + 1] += -1;
}
else {
pre[l] ++;
pre[i]--;
pre[i + 1]++;
pre[r + 1]--;
}
}
int ii = l - 1, jj = r + 1;
if (s[i] != s[j]) ii = i, jj = j;
if (ii < 1 || jj > n) continue;
l = 2, r = min(ii, n - jj + 1), rt = 1;
while (l <= r){
int mid = (l + r) >> 1;
int ps = jj + 1, ps2 = jj + mid - 1;
if (h1.gethsh(ii - mid + 1, ii - 1) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
rt = mid;
l = mid + 1;
}
else r = mid - 1;
}
f[s[ii] - 'a' + 1][jj] += rt;
f[s[jj] - 'a' + 1][ii] += rt;
}
}
int res = sum;
for (int i = 1; i <= n; i++){
pre[i] += pre[i - 1];
for (int j = 1; j <= 26; j++){
res = max(res , sum - pre[i] + f[j][i]);
}
}
cout << res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
18776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
