This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK 21
#define MN 300005
int n, cnt, ord[MK][MN], lcp[MK][MN], K, sc[MN];
char _S[MN], S[MN*2];
long long res;
struct data {
int a, b, x;
bool operator < (const data p) const {
if (a == p.a) return b < p.b;
return a < p.a;
}
} w[MN], v[MN];
void upd(int a, int b) {
int L = b-a+1, t = ord[K][a], lo = t, hi = t;
for (int i = K; i >= 0; i--) {
if (lo >= (1<<i) && lcp[i][lo-(1<<i)] >= L) lo -= (1<<i);
if (lcp[i][hi] >= L) hi += (1<<i);
}
res = max(res, (long long)(hi-lo+1)*L);
}
int main() {
int i, j;
scanf("%s",_S);
n = strlen(_S);
int k = 1, M = 'z';
for (i = 0; i < n; i++) v[i].a = _S[i], v[i].b = 0, v[i].x = i;
while (1) {
for (i = 0; i <= n-1; i++) sc[v[i].a]++;
for (i = 1; i <= M; i++) sc[i] += sc[i-1];
for (i = n-1; i >= 0; i--) w[--sc[v[i].a]] = v[i];
for (i = 1; i <= M; i++) sc[i] = 0;
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[K][w[i].x] = cnt;
}
if (k >= n) break;
M = cnt; cnt = n-1;
for (i = n-1; i >= 0; i--) {
if (w[i].x < k) continue;
v[cnt].a = ord[K][w[i].x-k], v[cnt].b = ord[K][w[i].x], v[cnt--].x = w[i].x-k;
}
for (i = n-k; i < n; i++) v[cnt].a = ord[K][i], v[cnt].b = 0, v[cnt--].x = i;
k <<= 1;
K++;
}
for (i = 1; i < n; i++) {
int w1 = w[i-1].x, w2 = w[i].x;
for (j = K; j >= 0; j--) if (ord[j][w1] == ord[j][w2]) w1 += (1<<j), w2 += (1<<j), lcp[0][i] += (1<<j);
}
for (i = 0; i < K; i++) for (j = 1; j < n-(1<<i); j++) lcp[i+1][j] = min(lcp[i][j], lcp[i][j+(1<<i)]);
for (i = 0; _S[i]; i++) S[i*2] = _S[i], S[i*2+1] = '-';
int m = n*2-1;
M = -1;
for (i = 0; i < m; i++) {
while (M+1 < m && M+1 <= i*2 && S[M+1] == S[i*2-(M+1)]) {
M++;
if (M&1) continue;
upd((i*2-M)/2, M/2);
}
}
printf("%lld", res);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |