#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;
int cnt[300005];
char s[300005], T[600005];
int P[20][300005], C[20][300005], RMQ[20][300005];
int LP[600005];
int lg[300005], SA[300005];
//void build_suffix_array(){
// for(int i = 1; i <= n ; ++i) C[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] = {C[k - 1][i], ((i + put) <= n) ? C[k - 1][i + put] : -1, i};
//
// sort(L + 1, L + n + 1);
// C[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) C[k][L[i].p] = C[k][L[i - 1].p];
// else C[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;
// }
// }
//}
void build_suffix_array(){
///P the sorted array of the positions
///C the equivalence class
for(int i = 1; i <= n ; ++i) ++cnt[s[i] - 'a'];
for(int i = 1; i < 26 ; ++i) cnt[i] += cnt[i - 1];
for(int i = 1; i <= n ; ++i) P[0][cnt[s[i] - 'a']--] = i;
C[0][P[0][1]] = 1;
int NR = 1;
for(int i = 2; i <= n ; ++i){
if(s[P[0][i]] != s[P[0][i - 1]]) ++NR;
C[0][P[0][i]] = NR;
}
for(int k = 1; k <= lgn ; ++k){
int put = (1 << (k - 1));
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n ; ++i){
SA[i] = P[k - 1][i] - put;
if(SA[i] < 0) SA[i] = (SA[i] % n + n) % n;
if(SA[i] == 0) SA[i] = n;
++cnt[C[k - 1][SA[i]]];
}
for(int i = 1; i <= NR ; ++i) cnt[i] += cnt[i - 1];
for(int i = 1; i <= n ; ++i) P[k][cnt[C[k - 1][SA[i]]]--] = SA[i];
NR = 1;
C[k][P[k][1]] = 1;
pair <int, int> p1, p2;
for(int i = 2; i <= n ; ++i){
int Next = P[k][i] + put, ok1 = 0;
if(Next > n) ok1 = 1;
int Next2 = P[k][i - 1] + put, ok2 = 0;
if(Next2 > n) ok2 = 1;
if(!ok1)
p1 = {C[k - 1][P[k][i]], C[k - 1][Next]};
else
p1 = {C[k - 1][P[k][i]], -1};
if(!ok2)
p2 = {C[k - 1][P[k][i - 1]], C[k - 1][Next2]};
else
p2 = {C[k - 1][P[k][i - 1]], -1};
if(p1 != p2) ++NR;
C[k][P[k][i]] = NR;
}
}
for(int i = 1; i <= n ; ++i) SA[i] = P[lgn][i];
}
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(C[k][x + ans] == C[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 = C[lgn][x], y = C[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 = C[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 = C[lgn][x] - mij;
dr = mij - 1;
}
else st = mij + 1;
}
st = C[lgn][x] + 1, dr = n;
while(st <= dr){
int mij = (st + dr) / 2;
if(use_lcp(x, SA[mij]) >= y - x + 1){
Sol2 = mij - C[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:155: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 |
6 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2944 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
2944 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3172 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3200 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
3200 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
12 ms |
5248 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
5240 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
26360 KB |
Output is correct |
| 2 |
Correct |
85 ms |
26332 KB |
Output is correct |
| 3 |
Incorrect |
83 ms |
26360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
74540 KB |
Output is correct |
| 2 |
Correct |
308 ms |
74644 KB |
Output is correct |
| 3 |
Incorrect |
228 ms |
74744 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
