Submission #5526

#	Time	Username	Problem	Language	Result	Execution time	Memory
5526		ainta	Palindromes (APIO14_palindrome)	C++98	100 / 100	760 ms	59388 KiB

palindrome

#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, Count[N_];
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_], tw[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, M = 'z';
	for (i = 0; p[i]; i++){
		tw[i].a = p[i], tw[i].b = 0, tw[i].num = i;
	}
	n = i;
	while (1){
		for (i = 0; i < n; i++){
			Count[tw[i].a]++;
		}
		for (i = 1; i <= M; i++)Count[i] += Count[i - 1];
		for (i = n - 1; i >= 0; i--){
			w[--Count[tw[i].a]] = tw[i];
		}
		for (i = 1; i <= M; i++)Count[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[C][w[i].num] = cnt;
		}
		if (K >= n) break;
		M = cnt;
		cnt = n - 1;
		for (i = n - 1; i >= 0; i--){
			if (w[i].num < K)continue;
			tw[cnt].a = ord[C][w[i].num - K];
			tw[cnt].b = ord[C][w[i].num];
			tw[cnt--].num = w[i].num - K;
		}
		for (i = n - K; i < n; i++){
			tw[cnt].a = ord[C][i];
			tw[cnt].b = 0;
			tw[cnt--].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);
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27