| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 5934 | tncks0121 | 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.
#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_];
int start[N_], link[N_], temp[N_];
int RMQ[lgN_][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 < 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];
link[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 = link[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;
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) {
x = CP[lgN_-1][x]; y = CP[lgN_-1][y];
if(x > y) swap(x, y);
if(x == y) return N;
int l = y-x; int k = lg2[l];
return min(RMQ[k][x], RMQ[k][y-(1<<k)]);
}
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], min(i - pm, 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;
}