| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 5524 | gs12117 | Palindromes (APIO14_palindrome) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define N_ 300010
#define SZ 524288
using namespace std;
int D[N_ * 2], n, ord[20][N_], LCP[20][N_], C;
long long Res;
char p[N_], q[N_ * 2];
struct A{
int a, b, num;
bool operator <(const A &p)const{
return a != p.a ? a<p.a : b<p.b;
}
}w[N_];
void Do(int b, int e){
int L = e - b + 1, t = ord[C][b], be = t, ed = t, i;
for (i = C; i >= 0; i--){
if (LCP[i][ed] >= L)ed += (1 << i);
}
for (i = C; i >= 0; i--){
if (be >= (1<<i) && LCP[i][be - (1<<i)] >= L)be -= (1 << i);
}
Res = max(Res, (long long)(ed - be + 1)*L);
}
void DP(){
int i, M = -1, mid, m;
for (i = 0; p[i]; i++){
q[i * 2] = p[i];
q[i * 2 + 1] = '-';
}
m = n * 2 - 1;
for (i = 0; i<m; i++){
if (M >= i){
if (D[mid * 2 - i] < M - i){
D[i] = D[mid * 2 - i];
continue;
}
}
mid = i;
while (M + 1 < m && M + 1 <= i * 2 && q[M + 1] == q[i * 2 - M - 1]){
M++;
if (M % 2 == 0){
Do((i * 2 - M) / 2, M / 2);
}
}
D[i] = M - i;
}
}
void SA(){
int i, K = 1, cnt;
for (i = 0; p[i]; i++){
w[i].a = p[i], w[i].b = 0, w[i].num = i;
}
n = i;
while (1){
sort(w, w + n);
cnt = 0;
for (i = 0; i<n; i++){
if (!i || w[i].a != w[i - 1].a || w[i].b != w[i - 1].b)cnt++;
ord[C][w[i].num] = cnt;
}
if (K >= n) break;
for (i = 0; i<n; i++){
w[i].a = ord[C][i];
if (K + i >= n)w[i].b = 0;
else w[i].b = ord[C][K + i];
w[i].num = i;
}
K *= 2;
C++;
}
}
int Gap(int a, int b){
int i, r = 0;
for (i = C; i >= 0; i--){
if (ord[i][a] == ord[i][b]){
a += (1 << i);
b += (1 << i);
r += (1 << i);
}
}
return r;
}
void PrePro(){
int i, j;
for (i = 0; i < n - 1; i++){
LCP[0][i+1] = Gap(w[i].num, w[i + 1].num);
}
for (i = 0; i < C; i++){
for (j = 1; j < n - (1 << i); j++){
LCP[i + 1][j] = min(LCP[i][j], LCP[i][j + (1 << i)]);
}
}
}
int main()
{
scanf("%s", p);
SA();
PrePro();
DP();
printf("%lld\n", Res);
}