import java.io.*;
class Main {
public static long M = (long) 1e9 + 9;
public static int P = 9973;
public static int N;
public static char[][] s;
public static long[][] hsh = new long[2][210001];
public static long[] pw = new long[210001];
public static long[][] extra = new long[210001][26];
public static long[] numPalindromes = new long[210001];
public static int[] deltaDelta = new int[210001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("palinap.in"));
PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("palinap.out")));
String tmp = br.readLine();
s = new char[2][(tmp.length() * 2) + 1];
for (int i = 0; i < tmp.length(); i++) {
s[0][i * 2] = '#';
s[0][i * 2 + 1] = tmp.charAt(i);
}
s[0][tmp.length() * 2] = '#';
N = s[0].length;
s[1] = s[0];
s[1] = reverse(s[1]);
hsh[0][0] = 1;
hsh[1][0] = 1;
pw[0] = 1;
for (int i = 0; i < N; i++) {
hsh[0][i + 1] = ((hsh[0][i] * P) % M + s[0][i]) % M;
hsh[1][i + 1] = ((hsh[1][i] * P) % M + s[1][i]) % M;
pw[i + 1] = pw[i] * P % M;
}
long base = 0;
for (int i = 0; i < N; i++) {
// calculate radius of palindrome
int lo = 0, hi = Integer.min(i, N - i - 1) + 1, r = 0;
while (lo < hi) {
int mid = (lo + hi) / 2;
boolean valid = getHash(i - mid, i, 0) == getHash(i, i + mid, 1);
if (valid) {
r = mid;
lo = mid + 1;
} else {
hi = mid;
}
}
if (r != 0) {
deltaDelta[i - r]++;
deltaDelta[i + 1] -= 2;
deltaDelta[i + r + 2]++;
}
base += (r + 1) / 2;
for (int j = 0; j < 26; j++) extra[i][j] += (r + 1) / 2;
int x = i - r - 1, y = i + r + 1;
if (x < 0 || x >= N || y < 0 || y >= N) continue;
// fix the boundary, calculate the new radius of palindrome
lo = 0;
hi = Integer.min(i - r - 1, N - (i + r + 1) - 1) + 1;
int r2 = 0;
while (lo < hi) {
int mid = (lo + hi) / 2;
boolean valid = getHash(i - r - 1 - mid, i - r - 2, 0) == getHash(i + r + 2, i + r + 1 + mid, 1);
if (valid) {
r2 = mid;
lo = mid + 1;
} else {
hi = mid;
}
}
r2++;
assert (s[0][x] != '#' && s[1][y] != '#');
extra[x][s[0][y] - 'a'] += r2 / 2;
extra[y][s[0][x] - 'a'] += r2 / 2;
}
long delta = 0, tot = 0;
for (int i = 0; i < N; i++) {
delta += deltaDelta[i];
tot += delta;
numPalindromes[i] = tot / 2;
}
long best = 0;
for (int i = 0; i < N; i++) {
if (i % 2 == 1) {
for (int j = 0; j < 26; j++) {
best = Long.max(best, extra[i][j] - numPalindromes[i]);
}
}
}
writer.println(base + best);
writer.close();
}
public static long getHash(int a, int b, int c) {
assert (a >= 0 && a < N && b >= 0 && b < N);
if (c == 1) {
int tmp = a;
a = N - 1 - b;
b = N - 1 - tmp;
}
return (hsh[c][b + 1] - (hsh[c][a] * pw[b - a + 1]) % M + M) % M;
}
public static char[] reverse(char a[]) {
char[] b = new char[a.length];
int j = a.length;
for (int i = 0; i < a.length; i++) {
b[j - 1] = a[i];
j = j - 1;
}
return b;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
184 ms |
12676 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
167 ms |
12252 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
12452 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
