#include <bits/stdc++.h>
using namespace std;
struct usu{
int x, y, p;
bool operator < (const usu &aux)const{
if(x != aux.x) return x < aux.x;
if(y != aux.y) return y < aux.y;
return p < aux.p;
}
};
usu L[300005];
int n, lgn;
char s[300005], T[600005];
int P[20][300005], RMQ[20][300005];
int LP[600005];
int lg[300005], SA[300005];
void build_suffix_array(){
for(int i = 1; i <= n ; ++i) P[0][i] = s[i] - 'a' + 1;
for(int k = 1; k <= lgn ; ++k){
int put = (1 << (k - 1));
for(int i = 1; i <= n ; ++i)
L[i] = {P[k - 1][i], ((i + put) <= n) ? P[k - 1][i + put] : -1, i};
sort(L + 1, L + n + 1);
P[k][L[1].p] = 1;
for(int i = 2; i <= n ; ++i){
if(L[i].x == L[i - 1].x && L[i].y == L[i - 1].y) P[k][L[i].p] = P[k][L[i - 1].p];
else P[k][L[i].p] = i;
}
if(k == lgn){
int NR = 0;
SA[++NR] = L[1].p;
for(int i = 2; i <= n ; ++i) SA[++NR] = L[i].p;
}
}
}
inline int find_lcp(int x, int y){
int ans = 0;
for(int k = lgn; k >= 0 ; --k){
if(max(x + ans, y + ans) > n) continue ;
if(P[k][x + ans] == P[k][y + ans]) ans += (1 << k);
}
return ans;
}
void build_lcp(){
for(int i = 1; i < n ; ++i) RMQ[0][i] = find_lcp(SA[i], SA[i + 1]);
for(int k = 1; k <= lgn ; ++k){
int put = (1 << (k - 1));
for(int i = 1; i <= n - (1 << k) ; ++i) RMQ[k][i] = min(RMQ[k - 1][i], RMQ[k - 1][i + put]);
}
}
inline int use_lcp(int x, int y){
if(x == y) return n - x + 1;
x = P[lgn][x], y = P[lgn][y];
if(x > y) swap(x, y);
int l = y - x, k = lg[l];
return min(RMQ[k][x], RMQ[k][y - (1 << k)]);
}
inline int nrap(int x, int y){
int st = 1, dr = P[lgn][x] - 1, Sol1 = 0, Sol2 = 0;
while(st <= dr){
int mij = (st + dr) / 2;
if(use_lcp(x, SA[mij]) >= y - x + 1){
Sol1 = P[lgn][x] - mij;
dr = mij - 1;
}
else st = mij + 1;
}
st = P[lgn][x] + 1, dr = n;
while(st <= dr){
int mij = (st + dr) / 2;
if(use_lcp(x, SA[mij]) >= y - x + 1){
Sol2 = mij - P[lgn][x];
st = mij + 1;
}
else dr = mij - 1;
}
return Sol1 + Sol2 + 1;
}
int main()
{
// freopen("palindrome.in", "r", stdin);
// freopen("palindrome.out", "w", stdout);
lg[1] = 0;
for(int i = 2; i <= 300000 ; ++i) lg[i] = lg[i / 2] + 1;
scanf("%s", s + 1);
n = strlen(s + 1);
lgn = 19;
build_suffix_array();
build_lcp();
///manacher-sama
int NR = 0;
T[++NR] = '.';
for(int i = 1; i <= n ; ++i) T[++NR] = s[i], T[++NR] = '.';
int R = 0, C = 0;
long long Sol = 0;
for(int i = 1; i <= NR ; ++i){
int rad = 0;
if(i <= R) rad = min(R - i, LP[2 * C - i]) + 1;
while(i + rad < NR && i - rad > 0 && T[i + rad] == T[i - rad]){
if((i + rad) % 2 == 0) Sol = max(Sol, 1LL * (rad + 1) * nrap((i - rad) / 2, (i + rad) / 2));
++rad;
}
LP[i] = rad - 1;
if(i + rad - 1 > R){
R = i + rad - 1;
C = i;
}
}
printf("%lld", Sol);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s + 1);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1664 KB |
Output is correct |
2 |
Correct |
5 ms |
1792 KB |
Output is correct |
3 |
Correct |
4 ms |
1664 KB |
Output is correct |
4 |
Correct |
3 ms |
1664 KB |
Output is correct |
5 |
Correct |
3 ms |
1664 KB |
Output is correct |
6 |
Correct |
3 ms |
1664 KB |
Output is correct |
7 |
Correct |
3 ms |
1664 KB |
Output is correct |
8 |
Correct |
3 ms |
1664 KB |
Output is correct |
9 |
Correct |
3 ms |
1664 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
3 ms |
1664 KB |
Output is correct |
12 |
Correct |
3 ms |
1664 KB |
Output is correct |
13 |
Correct |
3 ms |
1664 KB |
Output is correct |
14 |
Correct |
4 ms |
1664 KB |
Output is correct |
15 |
Correct |
4 ms |
1664 KB |
Output is correct |
16 |
Correct |
4 ms |
1664 KB |
Output is correct |
17 |
Correct |
4 ms |
1664 KB |
Output is correct |
18 |
Correct |
4 ms |
1664 KB |
Output is correct |
19 |
Correct |
3 ms |
1664 KB |
Output is correct |
20 |
Correct |
3 ms |
1664 KB |
Output is correct |
21 |
Correct |
4 ms |
1664 KB |
Output is correct |
22 |
Correct |
4 ms |
1664 KB |
Output is correct |
23 |
Correct |
3 ms |
1664 KB |
Output is correct |
24 |
Correct |
3 ms |
1664 KB |
Output is correct |
25 |
Correct |
4 ms |
1664 KB |
Output is correct |
26 |
Correct |
4 ms |
1664 KB |
Output is correct |
27 |
Correct |
3 ms |
1664 KB |
Output is correct |
28 |
Correct |
4 ms |
1664 KB |
Output is correct |
29 |
Correct |
3 ms |
1792 KB |
Output is correct |
30 |
Correct |
3 ms |
1664 KB |
Output is correct |
31 |
Correct |
4 ms |
1664 KB |
Output is correct |
32 |
Correct |
4 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1920 KB |
Output is correct |
2 |
Correct |
5 ms |
1920 KB |
Output is correct |
3 |
Correct |
5 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1920 KB |
Output is correct |
5 |
Correct |
5 ms |
1920 KB |
Output is correct |
6 |
Correct |
6 ms |
1920 KB |
Output is correct |
7 |
Correct |
5 ms |
1792 KB |
Output is correct |
8 |
Correct |
5 ms |
1920 KB |
Output is correct |
9 |
Correct |
5 ms |
1920 KB |
Output is correct |
10 |
Correct |
5 ms |
1920 KB |
Output is correct |
11 |
Correct |
6 ms |
1792 KB |
Output is correct |
12 |
Correct |
5 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
3328 KB |
Output is correct |
2 |
Correct |
16 ms |
3328 KB |
Output is correct |
3 |
Correct |
21 ms |
3328 KB |
Output is correct |
4 |
Correct |
25 ms |
3328 KB |
Output is correct |
5 |
Correct |
31 ms |
3204 KB |
Output is correct |
6 |
Correct |
23 ms |
3328 KB |
Output is correct |
7 |
Correct |
18 ms |
3300 KB |
Output is correct |
8 |
Correct |
25 ms |
3328 KB |
Output is correct |
9 |
Correct |
23 ms |
3192 KB |
Output is correct |
10 |
Correct |
28 ms |
3232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
18396 KB |
Output is correct |
2 |
Correct |
156 ms |
18456 KB |
Output is correct |
3 |
Correct |
242 ms |
18400 KB |
Output is correct |
4 |
Correct |
184 ms |
18552 KB |
Output is correct |
5 |
Correct |
410 ms |
18424 KB |
Output is correct |
6 |
Correct |
327 ms |
18424 KB |
Output is correct |
7 |
Correct |
228 ms |
18408 KB |
Output is correct |
8 |
Correct |
359 ms |
18424 KB |
Output is correct |
9 |
Correct |
338 ms |
18424 KB |
Output is correct |
10 |
Correct |
365 ms |
18440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
53284 KB |
Output is correct |
2 |
Correct |
558 ms |
53340 KB |
Output is correct |
3 |
Correct |
919 ms |
53340 KB |
Output is correct |
4 |
Correct |
658 ms |
53240 KB |
Output is correct |
5 |
Execution timed out |
1072 ms |
51448 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |