#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 300005, lgN_ = 19;
char S[N_]; int N;
int SA[N_], CP[lgN_][N_+N_];
int start[N_], lnk[N_], temp[N_];
int RMQ[lgN_][N_+N_];
int lg2[N_];
void build_suffix_array() {
for(int i = 1; i <= N; i++) SA[i] = i, CP[0][i] = S[i] - 'a' + 1;
for(int k = 0; k+1 < lgN_; k++) {
for(int c = 1; c >= 0; c--) {
for(int i = N; i > 0; i--) {
int x = SA[i] + (c<<k); if(x > N) x = 0;
int v = CP[k][x];
lnk[i] = start[v]; start[v] = i;
temp[i] = SA[i];
}
for(int i = 0, p = 0; i <= N || i <= 26; i++) {
for(int j = start[i]; j > 0; j = lnk[j]) SA[++p] = temp[j];
start[i] = -1;
}
}
int *now = CP[k], *nxt = CP[k+1];
nxt[SA[1]] = 1;
for(int i = 2, v = 1; i <= N; i++) {
int ap = now[SA[i-1]], bp = now[SA[i]];
int an = (SA[i-1] + (1<<k) <= N) ? now[SA[i-1] + (1<<k)] : 0;
int bn = (SA[i] + (1<<k) <= N) ? now[SA[i] + (1<<k)] : 0;
if(ap < bp || (ap == bp && an < bn)) ++v;
nxt[SA[i]] = v;
}
}
}
int lcp_logn (int x, int y) {
int r = 0;
if(x == y) return N-x+1;
for(int k = lgN_; --k >= 0; ) {
if(CP[k][x+r] == CP[k][y+r]) r += 1<<k;
}
return r;
}
void build_lcp () {
for(int i = 1; i < N; i++) RMQ[0][i] = lcp_logn(SA[i], SA[i+1]);
for(int i = 1, v = 0; i <= N; i++) v += (i>>v), lg2[i] = v-1;
for(int k = 1; k < lgN_; k++) {
for(int i = 1; i + (1<<k) - 1 <= N - 1; i++) RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1<<(k-1))]);
}
}
int lcp_constant (int x, int y) {
if(x == y) return N-x+1;
x = CP[lgN_-1][x]; y = CP[lgN_-1][y];
if(x > y) swap(x, y);
int l = y-x+1; int k = lg2[l];
//printf("%d %d: %d: %d\n", x, y, l, 1<<k);
return min(RMQ[k][x], RMQ[k][y-(1<<k)+1]);
}
int num_occurance (int x, int y) { // S[x..|S|]∞˙¿? √÷¿?∞???¡??Œª? ±?¿?∞° y-x+1 ¿?ª?¿?∏? ?
int w = CP[lgN_-1][x];
int low, high, ret1 = 0, ret2 = 0;
for(low = 1, high = w-1; low <= high; ) {
int mid = (low + high) >> 1;
if(lcp_constant(x, SA[mid]) >= y-x+1) {
ret1 = w - mid;
high = mid - 1;
}else {
low = mid + 1;
}
}
for(low = w+1, high = N; low <= high; ) {
int mid = (low + high) >> 1;
if(lcp_constant(x, SA[mid]) >= y-x+1) {
ret2 = mid - w;
low = mid + 1;
}else {
high = mid - 1;
}
}
return ret1 + ret2 + 1;
}
char T[N_+N_]; int TN;
int Table[N_+N_];
ll res;
int main() {
scanf("%s", S+1); N = strlen(S+1);
build_suffix_array();
build_lcp();
T[++TN] = '.';
for(int i = 1; i <= N; i++) T[++TN] = S[i], T[++TN] = '.';
int pr = -1, pm = -1;
for(int i = 1; i <= TN; i++) {
int &t = Table[i];
if(i <= pr) t = min(Table[pm + pm - i], pr - i);
while(i-t > 0 && i+t <= TN && T[i-t] == T[i+t]) {
if(pr < i+t) pr = i+t, pm = i;
if((i + t) % 2 == 0) res = max(res, (ll)(t + 1) * num_occurance((i - t) / 2, (i + t) / 2));
++t;
}
--t;
}
printf("%lld\n", res);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
99232 KB |
Output is correct - answer is '7' |
| 2 |
Incorrect |
0 ms |
99232 KB |
Output isn't correct - expected '4', found '3' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
